再写KMP算法

#include<iostream> #include<string> using namespace std; void getNext(char const*T,int len,int *next) { int i =0,j=-1; next[i] = -1; while(i<len) { if(j == -1 || T[i] == T[j]) { i++;j++;next[i] =j; } else j = next[j]; } } int KMP_search(char const*S,int slen,char const*T,int tlen,int *next) { int i=0,j=0; while(i<slen && j<tlen) { if(j==-1 || T[j] == S[i]) { j++;i++; } else j=next[j]; } return i-tlen; } int main() { string S="aabcabcebafabcabceabcaefabcacdabcab"; string T ="abac"; int *next = new int[T.size()]; getNext(T.data(),T.size(),next); for(int i = 0;i<T.size();i++) cout<<next[i]<<" "; cout<<endl; cout<<"The subString start with :"; cout<<KMP_search(S.data(),S.size(),T.data(),T.size(),next)<<endl; return 0; }

【参见】http://blog.csdn.net/yaochunnian/article/details/7059486

转载于:https://www.cnblogs.com/plxx/p/3801078.html