KMP算法-字符匹配

字符匹配模式-KMP算法

文章插图

文章插图
j直接跳到了2的位置，因为在之前的都相同。
那么就需要求如果不等了之后，j需要回跳的位置next[j]

文章插图

文章插图
如果tk'与tj相等，则next [j+1]=k'+1
如果tk‘与tj不相等，则继续向前找，直到找到next[0]=-1为止
注意：t是从0下标开始
1 void getnext(string t) 23 { 45int j=0,k=-1; 67int len=t.size(); 89next[0]=-1;10 11wihle(j<len)12 13{14 15if(k==-1||t[j]==t[k])16 17next[++j]==++k;18 19else20 21k=next[k];22 23}24 25 }得到next数组之后就可以进行枚举了，当s[i]!=t[j]时，就让j=next[j]然后再次进行讨论。
KMP匹配：
1 int KMP(string s,string t,int pos) 23 { 45int i=pos,j=0 67int lens=s.size(); 89int lent=t.size();10 11getnext(t);12 13while(i<lens&&j<lent)14 15{16 17if(j==-1||s[i]==t[j])18 19i++,j++;20 21else22 23j=next[j];24 25}26 27if(j>=lent)//匹配成功，则返回i-lent+1(即为t串出现的位置)28 29return i-lent+1;30 31else32 33return -1;34 35 }另外：
算法优化
当s[i]!=t[j]时,j=next[j]=k,如果t[j]=t[k],就没必要来比较,直接退回到next[k].
代码如下：
【KMP算法-字符匹配】 1 void getnext(string t) 2 { 3int j=0,k=-1; 4int len=t.size(); 5next[0]=-1; 6wihle(j<len) 7{ 8if(k==-1||t[j]==t[k]) 9{10j++,k++;11if(t[j]==t[k])12next[j]=next[k];//下一次要跳时就会直接从j跳到next[k];13else14next[j]=k;15}16else17k=next[k];18}19 }