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
30. 30

int kmp(string & S, string & T) {
	// Generate KMP table
	vector<int> F(T.size()+1, 0);
	F[0] = -1;
	for (int i = 0; i < T.size(); ++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.size()) {
		if (S[i] == T[j]) {
			++i, ++j;
			if (j == T.size()) return i - j; // Found match
			/*if (j == T.size()) {
				++ret; // Count matches
				j = F[j];
				if (j < 0) ++i, ++j;
			}*/
		}
		else {
			j = F[j];
			if (j < 0) ++i, ++j;
        }
	}

	return -1; // Match not found
}