哥也能写KMP了——实现strstr()
最后更新于:2022-04-01 09:33:00
经过上次去面试,[面试官要求实现strstr()](http://blog.csdn.net/kamsau/article/details/39352061),当场就蒙了。这个题目是模式匹配问题,《算法导论》里列出了几种字符串匹配算法:
朴素算法 | Rabin-Karp | 有限自动机算法 | Knuth-Morris-Pratt (KMP)
各种方法都有自己的优缺点,我觉得,还有一些方法可以参考:
1)比如像求最长公共子串那样,用动态规划,最后判断最长公共子串的最大值是不是模式串的长度,不过,这有点绕。
2)用后缀数组,这个也有点绕,实现起来也有点麻烦,就不说了。
个人觉得,还是KMP好,KMP该怎么写呢,立马抄起书《数据结构(C语言版)》,看了一下,感觉,KMP实现起来,代码是很少的,效率还算可以了,实现的过程中,难就难在如何构造next[] 数组,以及如何理解next[],对避免指针无效回退的作用。看了一个上午,总算是明白了。现就贴下代码,做下笔记。
~~~
#include<iostream>
using namespace std;
void get_next(const char* s, int* next){
int i = 0, j = -1;
next[0] = -1;
int len = strlen(s);
while(i < len){
if(j == -1 || s[i] == s[j]){
++i, ++j;
if(s[i] != s[j]) next[i] = j;
else next[i] = next[j];
}
else j = next[j];
}
}
int KMP_strstr(const char* s, const char* p){
int i = 0, j = 0;
int len_s = strlen(s), len_p = strlen(p);
int* next = new int[len_p];
get_next(s, next);
while(i < len_s && j < len_p){
if(j == -1 || s[i] == p[j])
++i, ++j;
else j = next[j];
}
delete []next;
if(j == len_p) return i - len_p;
else return -1;
}
int main(){
const int len = 6;
const char *s = "abaabc";
cout<<KMP_strstr("aaabbabaabcaad", s);
return 0;
}//output: 5
~~~