經過上次去面試，[面試官要求實現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
~~~
