kmp算法

图解KMP

首先说明前缀字符串不能包含最后一个字符，后缀字符串亦然

现在我们先看一个图：第一个长条代表主串，第二个长条代表子串。红色部分代表两串中已匹配的部分，

再具体一些：这个图代表主串”abcabeabcabcmn”和子串”abcabcmn”。

现在发现了不匹配的地方，根据KMP的思想我们要将子串向后移动，现在解决要移动多少的问题。

之前提到的最长相等前后缀的概念有用处了。因为红色部分也会有最长相等前后缀。如下图：

灰色部分就是红色部分字符串的最长相等前后缀，我们子串移动的结果就是让子串的红色部分最长相等前缀和主串红色部分最长相等后缀对齐。

这一步弄懂了，KMP算法的精髓就差不多掌握了。接下来的流程就是一个循环过程了。事实上，每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。

所以next[i]=j,含义是：下标为i 的字符前的字符串最长相等前后缀的长度为j。

我们可以算出，子串t= “abcabcmn”的next数组为next[0]=-1(前面没有字符串单独处理)

next[1]=0；next[2]=0；next[3]=0；next[4]=1；next[5]=2；next[6]=3；next[7]=0；

本例中的蓝色c处出现了不匹配（是s[5]!=t[5]）,

我们把子串移动，也就是让s[5]与t[5]前面字符串的最长相等前缀后一个字符再比较，而该字符的位置就是t[？],很明显这里的？是2，就是不匹配的字符前的字符串 最长相等前后缀的长度。

也是不匹配的字符处的next数组next[5]应该保存的值，也是子串回溯后应该对应的字符的下标。 所以？next[5]=2。接下来就是比对是s[5]和t[next[5]]的字符。这里也是最奇妙的地方，也是为什么KMP算法的代码可以那么简洁优雅的关键。

我们可以总结一下，next数组作用有两个：

一是之前提到的，

next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

二是：

表示该处字符不匹配时应该回溯到的字符的下标

next有这两个作用的源头是：之前提到的字符串的最长相等前后缀

KMP算法的时间复杂度

现在我们分析一下KMP算法的时间复杂度：

KMP算法中多了一个求数组的过程，多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m)，因后面匹配中主串不回溯，比较次数可记为n，所以KMP算法的总时间复杂度为O(m+n)，空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n)，KMP算法提速是非常大的，这一点点空间消耗换得极高的时间提速是非常有意义的，这种思想也是很重要的。

下面还有更厉害的，我们一起来分析具体的代码。

求next数组的代码

下面我们一起来欣赏计算机如何求得next数组的

typedef struct
{	
	char data[MaxSize];
	int length;			//串长
} SqString;
//SqString 是串的数据结构
//typedef重命名结构体变量，可以用SqString t定义一个结构体。
void GetNext(SqString t,int next[])		//由模式串t求出next值
{
	int j,k;
	j=0;k=-1;
	next[0]=-1;//第一个字符前无字符串，给值-1
	while (j<t.length-1) 
	//因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
	//所以最后一次经过while循环时j为t.length-2
	{	
		if (k==-1 || t.data[j]==t.data[k]) 	//k为-1或比较的字符相等时
		{	
			j++;k++;
			next[j]=k;
			//对应字符匹配情况下，s与t指向同步后移
			//通过字符串"aaaaab"求next数组过程想一下这一步的意义
			//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
       	}
       	else
		{
			k=next[k];
			**//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
			//也表示该处字符不匹配时应该回溯到的字符的下标
			//这个值给k后又进行while循环判断，此时t.data[k]即指最长相等前缀后一个字符**
			//为什么要回退此处进行比较，我们往下接着看。其实原理和上面介绍的KMP原理差不多
			//printf("(2) k=%d\n",k);
		}
	}
}

解释next数组构造过程中的回溯问题

大家来看下面的图：

下面的长条代表子串，红色部分代表当前匹配上的最长相等前后缀，蓝 色部分代表t.data[j]。

KMP算法代码解释

int KMPIndex(SqString s,SqString t)  //KMP算法
{
    //s代表大串，t代表小串
	int next[MaxSize],i=0,j=0;
	GetNext(t,next);
	while (i<s.length && j<t.length) 
	{
		if (j==-1 || s.data[i]==t.data[j]) 
		{
			i++;j++;  			//i,j各增1
		}
		else j=next[j]; 		//i不变,j后退，现在知道为什么这样让子串回退了吧
    }
    if (j>=t.length)
		return(i-t.length);  	//返回匹配模式串的首字符下标
    else  
		return(-1);        		//返回不匹配标志
}

KMP算法的改进

为什么KMP算法这么强大了还需要改进呢？

大家来看一个例子:

主串s=“aaaaabaaaaac”

子串t=“aaaaac”

这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。’c’前的’a’回溯后的字符依然是‘a’。

我们知道没有必要再将‘b’与‘a’比对了，因为回溯后的字符和原字符是相同的，原字符不匹配，回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为：nextval数组。KMP算法的改进可以简述为： 如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next值。 这应该是最浅显的解释了。如字符串”ababaaab”的next数组以及nextval数组分别为：

我们来分析下代码：

void GetNextval(SqString t,int nextval[])  
//由模式串t求出nextval值
{
	int j=0,k=-1;
	nextval[0]=-1;
   	while (j<t.length-1) 
	{
       	if (k==-1 || t.data[j]==t.data[k]) 
		{	
			j++;k++;
			if (t.data[j]!=t.data[k]) 
//这里的t.data[k]是t.data[j]处字符不匹配而会回溯到的字符
//为什么？因为没有这处if判断的话，此处代码是next[j]=k;
//next[j]不就是t.data[j]不匹配时应该回溯到的字符位置嘛
				nextval[j]=k;
           	else  
				nextval[j]=nextval[k];
//这一个代码含义是不是呼之欲出了？
//此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
//用较为粗鄙语言表诉：即字符不匹配时回溯两层后对应的字符下标
       	}
       	else  k=nextval[k];    	
	}

}

int KMPIndex1(SqString s,SqString t)    
//修正的KMP算法
//只是next换成了nextval
{
	int nextval[MaxSize],i=0,j=0;
	GetNextval(t,nextval);
	while (i<s.length && j<t.length) 
	{
		if (j==-1 || s.data[i]==t.data[j]) 
		{	
			i++;j++;	
		}
		else j=nextval[j];
	}
	if (j>=t.length)  
		return(i-t.length);
	else
		return(-1);
}

hdu1358

题目：

思路：

题目是找出所有能形成大于一次的循环前缀子串，并包含该字符串本身

然后类似poj 2406的求法

代码：

#include <stdio.h>
#include <string.h>
using namespace std;
char c[1000001];
int next[1000001];	// 注意数组大小哈~。~
int len;

// 求next数组
void Get_next()
{
    int i,j;
	next[0]=-1;
	i=0;
	j=-1;
	while(i<len)
	{
	    if(j==-1 || c[i]==c[j])
	    {
	       next[++i]=++j;
	    }
	    else    j=next[j];
	}
}

void show(void)
{
    int i,n;
	// 如果c[i-1]的话要跳过的，详情可以看我下面链接
    for(i=2;c[i-1];++i)
    {
        n=i-next[i];
        if(i%n==0 && i/n>1)
        {
            printf("%d %d\n",i,i/n);
        }
    }
    return;
}

int main()
{
    int num=1;
    while(scanf("%d",&len)!=EOF)
    {
        if(len==0)    break;
	    memset(next,0,sizeof(next));
	    scanf("%s",c);

Get_next();

printf("Test case #%d\n",num++);
        show();
		// 注意格式啊！这个换行又坑了我一次WA
        printf("\n");
    }
	return 0;
}

hdu 1711

题目：

思路：

kmp模板题

代码：

#include<stdio.h>
#include<string.h>
#define N 1000005
int s[N];
int p[N];
int next[N];
int m,n;
void getnext(){
    int j=0,k=-1;
    next[0]=-1;
    while(j<m){
        if(k==-1||p[j]==p[k]){
            j++;
            k++;
            next[j]=k;
        }
        else
            k=next[k];
    }
}
int kmp(){
    int i=0,j=0;
    getnext();
    while(i<n){
        if(j==-1||s[i]==p[j]){
            i++;
            j++;
        }
        else
            j=next[j];
        if(j==m)
            return i;
    }
    return -1;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%d",&s[i]);
        for(int i=0;i<m;i++)
            scanf("%d",&p[i]);
        if(kmp()==-1)
            printf("-1\n");
        else
            printf("%d\n",kmp()-m+1);
    }
    return 0;
}

hdu 2087

题目：

思路：

简单的kmp应用，右手就行

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string a;
string b;
int Next[1005];
int lena,lenb;
void getNext()
{
    int i=0,j=-1;
    Next[0]=-1;
    while(i<lenb-1)
    {
        if(j==-1||b[i]==b[j])
        {
            i++;
            j++;
            Next[i]=j;
        }
        else j=Next[j];
    }
}

int main()
{
    while(1)
    {
        cin>>a;
        if(a[0]=='#')break;
        cin>>b;
        lena=a.size();
        lenb=b.size();
        getNext();
        int i=0,j=0,sum=0;
        while(i<=lena)
        {
            if(j==lenb)
            {
                sum++;
                j=0;
            }
            if(j==-1||a[i]==b[j])
            {
                i++;
                j++;
            }
            else j=Next[j];
        }
        cout<<sum<<endl;
    }
    return 0;
}       

poj 2406

题目：

思路：

找kmp规律的题目，根据循环节不是本身，则其长度一定被该字符串整除的规律

  我们有结论：若n%(n−p[n])==0，最小循环节长度为n/(n−p[n])；否则就为它本身。

  我们对着证明考虑两部分，一是可以整除时为什么这是答案，而是为什么不能整除是最小循环节为它本身。

  ①如果n是(n−p[n])的倍数，我们可以把字符串分为若干段长(n−p[n])的字符串。首先我们把每段记为A、B、C、D(假设只有四段)，所以D段表示的是字符串S[p[n]，n]这一段，而由P数组的定义我们可知p[n]表示的n的最长公共前后缀，即S[1…p[n]]前缀和S[p[n]…n]后缀相同，所以我们有ABC=BCD(表示字符串依次连接)，由于它们完全相等，所以A=B，B=C，C=D，所以可知A就是循环节，而很容易由反证法知道不存在更短的循环节，否则和p数组定义不符。其数目即为答案。

  ②我们需要解决为什么不整除时就最小循环节就是它本身。我们运用反证法，假设存在最小循环节长len(len！=n)，那么S[1，len]=S[n−len，n]，那么len=n−p[n]，而由假设知，n不被n−p[n]整除，但又由循环节定义知n被len整除，因此矛盾。

代码：

include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int pre[MAXN];
char s[MAXN];
int main() 
{
    while(~scanf(" %s",s+1))
    {
        int n=strlen(s+1);
        if(s[1]=='.')break ;
        int j=0;pre[1]=0;
        for(int i=1;i<n;i++)
        {
            while(j>0&&s[i+1]!=s[j+1])j=pre[j];
            if(s[i+1]==s[j+1])j++;
            pre[i+1]=j;
        }
        if(n%(n-pre[n])==0)printf("%d\n",n/(n-pre[n]));
        else printf("1\n");
    }
    return 0;
}

hdu3336

题目：

思路：

考了kmp算法中next数组的创建思路，合理遍历了整个字符串，注意的是：本来next[length]是不会被使用到的（因为那个位置压根就没有字符，会被直接存在子串与模板串相同），但是由于本题需要考虑后缀子串与前缀字串可能存在的相等情况，所以需要遍历到next[length]

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 10007;
string s;
int Next[200001];
int len;
void getNext()
{
    Next[0]=-1;
    int i=0,j=-1;
    while(i<len)
    {
        if(j==-1||s[i]==s[j])
        {
            ++i;
            ++j;
            Next[i]=j;
        }
        else j=Next[j];
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {

scanf("%d",&len);
        cin>>s;
        getNext();
        int sum=0;
        for(int i=1;i<=len;i++)
        {
            int j=i;
            while(j>0)
            {
                sum=(sum+1)%mod;
                j=Next[j];
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}