Untitled

/// KMP - O(N + M)
/// Memory - O(M)

#include <bits/stdc++.h>
using namespace std;

void computeLPSArray(string pat, int M, int *lps) {
	int len = 0;

	lps[0] = 0;

	int i = 1;
	while (i < M) {
		if (pat[i] == pat[len]) {
			++len;
			lps[i] = len;
			++i;
		}
		else {
			if (len != 0) len = lps[len - 1];
			else lps[i] = 0, ++i;
		}
	}
}

void kmp(string txt, string pat) {
	int N = (int)txt.size();
	int M = (int)pat.size();

	int lps[M]; /////

	computeLPSArray(pat, M, lps);

	int i = 0, j = 0;
	while ((N - i) >= (M - j)) {
		if (pat[j] == txt[i]) ++j, ++i;

		if (j == M) {
			cout<<"Found pattern at index "<<i - j<<'\n'; ////////
			j = lps[j - 1];
		}

		else if (i < N && pat[j] != txt[i]) {
			if (j != 0) j = lps[j - 1];
			else i = i + 1;
		}
	}
}

int main() {
	string txt = "abcabca";
	string pat = "abc";
	kmp(txt, pat);
}