/**KMP算法算法思想：T0….T(j-i)……T(j-1) Tj==!=p0P(i-1) Pi即在比较的过程中有P(0…i-1) = T(j-i….j-1) 再往下匹配时 Pi =！Tj如果找到K值使P(0..i-k-1) = p(k..i-1)这样字符创P可以移动K位因为P(k..i-1)与Tj-1前面的i-1-K为相等所以P(0..i-k-1)也与Tj-1前面的i-1-K为相等因此只需要比较P(i-k) 和Tj就行了*/#include <iostream>#include <string>using namespace std;/**寻找模式串P每个字符的特征数即每个字符前P(0…i-1)的最大相同前缀子串和后缀子串Next(i) = -1当i = 0使max{k:0 < k < i && P(0…k-1) = P(i-k…i-1) } K存在0K不存在*/int * findNext(string P){int i = 0;int m = P.length();int * Next = new int[m];Next[0] = -1;int k = -1;//从开始0-m-1循环，计算 i= 0…m-1的next的值while(i < m){//求最大的首位子串while(k >= 0 && P[i] != P[k]){/**用到前边所求的next的值因为是要每次都是从P的开始位置匹配next[i]的值就是在第i个字符前面串的最大相同前缀和后缀子串而P[k]是P的第k个字符，现在P[k]和P[i]不相等，我们应该从第k的字符的最大相同前缀和后缀子串的位置开始重新匹配而第K个字符的最大相同前缀和后缀子串的位置是next[k]就是相当于把P串看成要匹配的串*/k = Next[k];}i ++;k ++;if(i == m) break;//如果P[i] 和 P[k] 相等，优化/**如果P[i] 和 P[k] 相等则P[k]也不会和Tj相等还需要向右移动*/if(P[i] == P[k]){Next[i] = Next[k];}elseNext[i] = k;}return Next;}int KMP(const string & T ,const string & P , int * Next){int tLen = T.length();int pLen = P.length();int i = 0;int j = 0;if(tLen < pLen) return -1;while(i < tLen && j < pLen){if(j == -1 || T[i] == P[j]){i ++;j ++;//cout<<"j:"<<j<<endl;}else{//如果不匹配，，返回到最大前缀后缀子串处去匹配j = Next[j];}}//最后检验结果，若果j的值大于P的长度是说明子串的位置已经找到if(j >= pLen){return (i – pLen + 1);}else return -1;}int main(){//cout << "Hello world!" << endl;string T = "abcdaabcab";string P = "abc";int * Next = findNext(P);for(int i = 0 ; i < P.length() ; i ++){cout<<Next[i]<<" ";}cout<<endl;int j = KMP(T,P,Next);cout<<j<<endl;return 0;}
你必须百分之百的把自己推销给自己。
