```
class Solution {
public:
int strStr(char *haystack, char *needle) {
int n = strlen(haystack);
int m = strlen(needle);
if (m == 0) return 0;
/*Counting prefix function for needle*/
int *p = new int[m];
for (int i = 0; i < m; i++)
p[i] = 0;
for (int i = 1; i < m; i++) {
p[i] = p[i - 1];
while (p[i] > 0 && needle[p[i]] != needle[i])
p[i] = p[p[i] - 1];
if (needle[p[i]] == needle[i])
p[i]++;
}
/***********************************/
/*KMP algo*/
int pre = 0;
for (int i = 0; i < n; i++) {
while (pre > 0 && needle[pre] != haystack[i])
pre = p[pre - 1];
if (needle[pre] == haystack[i]) pre++;
if (pre == m) {
return i - pre + 1;
}
}
/*********/
return -1;
}
};
```