1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29

#include <string>
#include <vector>
using namespace std;

int KMP(string &S, string &T) {
	// Generate KMP table
	vector<int> F(T.length() + 1, 0);
	F[0] = -1;
	for (int i = 0; i < T.length(); i++) {
		F[i + 1] = F[i];
		while (F[i + 1] > -1 && T[i] != T[F[i + 1]]) F[i + 1] = F[F[i + 1]];
		F[i + 1]++;
	}

	// Search
	int i = 0, j = 0;
	while (i < S.length()) {
		if (S[i] == T[j]) {
			i++, j++;
			if (j == T.length()) return i - j; // Found match
		}
		else {
			j = F[j];
			if (j < 0) i++, j++;
		}
	}

	return -1; // Match not found
}