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)
 2 
 3 {
 4 
 5      int j=0,k=-1;
 6 
 7      int len=t.size();
 8 
 9      next[0]=-1;
10 
11      wihle(j<len)
12 
13      {
14 
15          if(k==-1||t[j]==t[k])
16 
17               next[++j]==++k;
18 
19          else
20 
21               k=next[k];
22 
23      }
24 
25 }

得到next数组之后就可以进行枚举了，当s[i]!=t[j]时，就让j=next[j]然后再次进行讨论。

KMP匹配：

 1 int KMP(string s,string t,int pos)
 2 
 3 {
 4 
 5      int i=pos,j=0
 6 
 7      int lens=s.size();
 8 
 9      int lent=t.size();
10 
11      getnext(t);
12 
13      while(i<lens&&j<lent)
14 
15      {
16 
17          if(j==-1||s[i]==t[j])
18 
19               i++,j++;
20 
21          else
22 
23               j=next[j];
24 
25      }
26 
27      if(j>=lent)//匹配成功，则返回i-lent+1(即为t串出现的位置)
28 
29          return i-lent+1;
30 
31      else
32 
33          return -1;
34 
35 }

另外：

算法优化

当s[i]!=t[j]时,j=next[j]=k,如果t[j]=t[k],就没必要来比较,直接退回到next[k].

代码如下：

 1 void getnext(string t)
 2 {
 3        int j=0,k=-1;
 4        int len=t.size();
 5        next[0]=-1;
 6        wihle(j<len)
 7        {
 8               if(k==-1||t[j]==t[k])
 9               {
10                      j++,k++;
11                      if(t[j]==t[k])
12                             next[j]=next[k];//下一次要跳时就会直接从j跳到next[k];
13                      else
14                             next[j]=k;
15               }
16               else
17                     k=next[k];
18        }
19 }