class Solution {
public:
	int strStr(string haystack, string needle) {
		int n = haystack.size();
		int m = needle.size();
		if (m == 0) {
			return 0;
		}
		vector<int> pi(m);
		for (int i = 1, j = 0; i < m; i++) {
			while (j > 0 && needle[i] != needle[j]) {
				j = pi[j - 1];
			}
			if (needle[i] == needle[j]) {
				j++;