Question:
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
Anwser 1: O(n*m)
class Solution {
public:
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int haylen = strlen(haystack);
int needlen = strlen(needle);
for(int i = 0; i <= haylen - needlen; i++){
char *p = haystack + i;
char *q = needle;
while(*q != '\0'){
if(*p != *q){
break;
} else {
p++;
q++;
}
}
if(*q == '\0'){
return haystack + i;
}
}
return NULL;
}
};
Anwser 2: O(n + m) KMP
class Solution {
public:
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int haylen = strlen(haystack);
int needlen = strlen(needle);
int* fail = new int[needlen];
memset(fail, -1, needlen * sizeof(int)); // strlen(fail)
int i, j, k;
for (i = 1; i < needlen; ++i) {
for (k = fail[i-1]; k >= 0 && needle[i] != needle[k+1]; k = fail[k]);
if (needle[k+1] == needle[i])
fail[i] = k + 1;
}
i = j = 0;
while(i < haylen && j < needlen) // while(haystack[i] && needle[j])
{
if (haystack[i] == needle[j])
{
++i;
++j;
}
else if(j == 0) ++i;
else j = fail[j-1] + 1;
}
delete fail;
/*
if (needle[j]) {
return NULL;
} else {
return haystack + i - j;
}*/
if(j == needlen){
return haystack + i - j;
} else {
return NULL;
}
}
};
参考推荐: