LeetCode_implement strstr ()
3879 ワード
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 calculatNext(char *pattern)
{
int i = 0, k = -1;
next[0] = -1;
while( i < sizeNeed -1) // next[i+1]
{
while(k >= 0 && pattern[i] != pattern[k]) k = next[k];
i++; k++;
next[i] = pattern[i] == pattern[k] ? next[k] : k;
}
}
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sizeHay = strlen(haystack);
sizeNeed = strlen(needle);
if(sizeNeed == 0) return haystack;
next.resize(sizeNeed);
calculatNext(needle);
int i = 0, j = 0;
while(i< sizeHay && j < sizeNeed)
{
if(j == -1 || haystack[i] == needle[j]){
i++;j++;
}else
j = next[j];
}
if(j >= sizeNeed)
return haystack+(i - j);
else
return NULL ;
}
private :
int sizeHay;
int sizeNeed ;
vector<int> next ;
};