class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
int i, q;
int *next = new int[m];
getNext(needle, next);
for(i = 0, q = 0; i < n; i++){
while(q > 0 && haystack[i] != needle[q])
q = next[q-1];
if(haystack[i] == needle[q])
q++;
if(q == m)
return i-q+1;
}
return -1;
}
void getNext(const string& pattern, int next[]){
int m = pattern.size();
int k;
next[0] = 0;
for(int q = 1, k = 0; q < m; q++){
while(k > 0 && pattern[q] != pattern[k])
k = next[k-1];
/*pattern[0...k-1]能匹配，pattern[k]待匹配 ,不行就再缩小k的范围*/
if(pattern[q] == pattern[k])
k++;
next[q] = k;
}
/*经典示例：ababzababa */
}
};
KMP算法
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 最近在leetcode上刷题，当然，是用swift，中间的辛酸经历就不提了，不得不说swift在便利性上的确十分强...
