kmp算法

发表于 | 分类于

我会结合代码对KMP算法进行详细讲解。由于编代码和做数据结构的题不一样所以，我分两部分对KMP进行讲解。首先，大家要了解一个字符串的前后缀不能是这个字符串本身。大家先记住这个条件，下面会用到。

手算next串

书上对next串求法的定义是这样的：

根据书中定义很难理解next串是如何求解的。 根据一个例子来具体讲解如何手算next串。

j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c

根据定义很容易知道next[1]=0(注意，这里下表是从1开始)

j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0              

接下来就需要根据定义中第二个公式依次求解。 首先要明白这个公式表达的是什么意思$Max(k|1<k<j且有”t_1t_2…t_{k-1}”=”t_{j-k+1}t_{j-k+2}…t_{j-1}”)$，其实这个公式求得就是j-1的最长公共前后缀。$”t_1t_2…t_{k-1}”=”t_{j-k+1}t_{j-k+2}…t_{j-1}$这个式子可以看出是在匹配找最大相同前后缀。最终结果为最长前后缀加一(解释加一的原因，仔细观察Max函数，$t_1t_2…t_{k-1}$最终是以k-1结尾，我们取的是k),就拿上面的例子来说，j取5。 因为$t_{j-k+1}t_{j-k+2}…t_{j-1}$,所以最多只能匹配到第j-1=4位。

1 2 3 4
a b a a

可以看出他们的最长相同前后缀为a,长度为1 所以j=5时，next[5]=2. 在举个j=6时，

1 2 3 4 5
a b a a b

所以最长相同前后缀为ab,长度为2，则next[6]=3,然后依次求出所有next,得

j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2

最后还有一个疑问可能是，最后的(next[j]=1,其他情况)是干什么的。因为存在没有任何公共前后缀的情况，所以给这些对应的位置赋值为一，如果对匹配过程比较熟悉的话因该就会知道，这个一其实就是让模式串从头开始匹配。其实最后一个式子基本用不到，因为按第二个公式也能求出一，没有匹配到相同的前后缀，直接取零，然后加一就行了。

编程计算next串

在这里我用c++对算法进行实现。

1
2
3
4
5
6
7
8
9
10
11
void getNext(){
    int i=0,j=-1;
    int len=strlen(pattern);
    while(j==-1||i<len){
        if(j==-1||pattern[i]==pattern[j]){
            Next[++i] =++j;
        }else{
            j=Next[j];
        }
    }
}

这里需要注意，计算机数组下标是从零开始的 还是这个例子，这个是上面的算法求出的next数组，和上面的比较一下，其实是让每一位都减了一。

j 0 1 2 3 4 5 6 7
模式串 a b a a b c a c
next[j] -1 0 0 1 1 2 0 1

然后详细讲解实现过程，我们将模式串拷贝一份，一份叫做假主串，一串叫做假模式串。这里这样叫是为了让大家不和匹配过程混淆。 我会按照算法匹配的过程实现一下。 next[0]=-1,不用计算，由上面的公式可知，求next[j]的值时，$t$最多只能取到$t_{j-1}$，所以求一个串的最长公共前后缀是根据要求的下标之前的串确定的。 i=0, j=-1,初始位置

    0 1 2 3 4 5 6 7
i下标指向   i              
假主串   a b a a b c a c
假模式串   a b a a b c a c
  -1 0 1 2 3 4 5 6 7
j下标指向 j                

执行$next[++i]=++j.next[1]=0$
$i=1,j=0$

    0 1 2 3 4 5 6 7  
i下标指向     i              
假主串   a b              
假模式串     a b            
    -1 0 1 2 3 4 5 6 7
j下标指向     j              

pattern.at(i)==pattern.at(j)不相等，执行else语句，j=next[j],即j=next[0]=-1,因为j=-1,所以又执行$next[++i]=++j;next[2]=0$
$i=2,j=0$

    0 1 2 3 4 5 6 7    
i下标指向       i              
假主串   a b a              
假模式串       a b a          
      -1 0 1 2 3 4 5 6 7
j下标指向       j              

执行$next[++i]=++j.next[3]=1$
$i=3,j=1$

    0 1 2 3 4 5 6 7    
i下标指向         i            
假主串   a b a a            
假模式串       a b a a        
      -1 0 1 2 3 4 5 6 7
j下标指向         j            

$j=next[j]=next[1]=0$

    0 1 2 3 4 5 6 7      
i下标指向         i              
假主串   a b a a              
假模式串         a b a a        
        -1 0 1 2 3 4 5 6 7
j下标指向         j              

执行$next[++i]=++j,next[4]=1$
$i=4,j=1$

    0 1 2 3 4 5 6 7      
i下标指向           i            
假主串   a b a a b            
假模式串         a b a a b      
        -1 0 1 2 3 4 5 6 7
j下标指向           j            

执行$next[++i]=++j.next[5]=2$
$i=5,j=2$

    0 1 2 3 4 5 6 7      
i下标指向             i          
假主串   a b a a b c          
假模式串         a b a a b c    
        -1 0 1 2 3 4 5 6 7
j下标指向             j          

执行$j=next[j]=next[2]=0$

    0 1 2 3 4 5 6 7          
i下标指向             i              
假主串   a b a a b c              
假模式串             a b a a b c    
            -1 0 1 2 3 4 5 6 7
j下标指向             j              

执行$j=next[j]=-1$ 执行$next[++i]=++j,next[6]=0$ $i=6,j=0$

    0 1 2 3 4 5 6 7            
i下标指向               i              
假主串   a b a a b c a              
假模式串               a b a a b c a  
              -1 0 1 2 3 4 5 6 7
j下标指向               j              

执行$next[++i]=++j.next[7]=1$. 其实执行到这里已经结束了 $i=7,j=1$

    0 1 2 3 4 5 6 7            
i下标指向                 i            
假主串   a b a a b c a c            
假模式串               a b a a b c a c
              -1 0 1 2 3 4 5 6 7
j下标指向                 j            

执行$j=next[1]=0$,不匹配，继续执行$j=next[0]=-1$ $next[++i]=++j.next[8]=1$ 我们显然不需要下标为8的next,但是有一种题是需要这个下标的。 如杭电的这一题：http://acm.hdu.edu.cn/showproblem.php?pid=1686 如果大家仅仅求next串,只需将len-1。（建议不减，不影响最终结果） 根据一步步执行大家可以看出是不是和我们手算最长公共前后缀是不是很像。

最后将完整代码贴出来。这个是上面那道题的题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstring>
using namespace std;
int Next[1000010];
char s[1000010];
char pattern[1000010];
void getNext(){
    int i=0,j=-1;
    int len=strlen(pattern);
    while(j==-1||i<len){
        if(j==-1||pattern[i]==pattern[j]){
            Next[++i] =++j;
        }else{
            j=Next[j];
        }
    }
}
int kmp(){
    int i=0,j=0;
    int ans=0;
    int len1=strlen(s);
    int len2=strlen(pattern);
    while(i<len1){
        if(j==-1||s[i]==pattern[j]){
            i++;j++;
        }else{
            j=Next[j];
        }
        if(j==len2){
        	ans++;
		}
    }
    return ans;
    
}
int main(){
    int t;
    cin>>t;
    while(t--){
    	cin>>pattern>>s;
    	Next[0]=-1;
	    getNext();
	    int k=kmp();
	    cout<<k<<endl;
	}
	return 0; 
}