Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
思路：这是非常典型的KMP算法题。
class Solution {
public:
void computePrefix(char* needle, int* next)
{
int m = strlen(needle);
int i = 0, j = -1;
next[0] = -1;
while(needle[i] != '\0')
{
while (j >= 0 && needle[j] != needle[i])
{
j = next[j];
}
++i, ++j;
next[i] = j;
}
}
char *strStr(char *haystack, char *needle) {
if (strcmp(haystack, needle) == 0)
{
return haystack;
}
int m = strlen(needle);
int n = strlen(haystack);
if (m == 0)
{
return haystack;
}
int next[m];
int i = 0, j = 0;
computePrefix(needle, next);
while(haystack[i] != '\0')
{
while(j >= 0 && haystack[i] != needle[j])
j = next[j];
++i, ++j;
if (needle[j] == '\0')
{
return haystack + i - j;
}
}
return NULL;
}
};