KMP算法模板

$Next[i]Next[i]$数组表示字符串$p[0]\sim p[i-1]p[0]\backslash sim\; p[i-1]$除自身以外的最长相同前缀和后缀的长度

$Next[j]Next[j]$表示当$p[j]p[j]$失配时，j回溯的位置。还有以下含义 1.匹配串$pp$能向右滑动尽可能远的距离（辅助理解而已） 2.前$j-1j-1$个字符串中，前缀字符串和后缀字符串的最大匹配长度。（后面有应用）

#include<bits stdc++.h>
using namespace std;
const int MAXN=1000+5;
char str[MAXN],pattern[MAXN];
int Next[MAXN];
int cnt;
int getFail(char *p,int plen){
			//预计算Next[],用于在失配的情况下得到j回溯的位置
	Next[0]=0;	Next[1]=0;
	for(int i=1;i<plen;i++){ int j="Next[j];" while(j&&p[i]!="p[j])" next[i+1]="(p[i]==p[j])?j+1:0;" } kmp(char *s,char *p){ 在s中找p last="-1;" slen="strlen(s),plen=strlen(p);" getfail(p,plen); 预计算next[]数组 for(int i="0;i<slen;i++){" 匹配s和p的每一个字符 while(j&&s[i]!="p[j])" 失配了，用next[]找j回溯位置 if(s[i]="=p[j])" j++; 当前位置的字符匹配，继续 if(j="=plen){" 这个匹配，在s中的起点是i+1-plen,末尾是i,如有需要可以打印 printf("at location="%d," %s\n",i+1-plen,&s[i+1-plen]); ---------------下面是与本题有关的工作 if(i-last>=plen){				//判断新的匹配和上一个匹配是否能分开 
				cnt++;
				last=i;						//last指向上一次匹配的末尾位置； 
			} 
			//----------------
		}
	} 
}
int main(){
	while(~scanf("%s",str)){
		if(str[0]=='#')	break;
		scanf("%s",pattern);
		cnt=0;
		kmp(str,pattern);
		printf("%d\n",cnt);
	}
} 

优化了Next数组后：

#include<bits stdc++.h>
using namespace std;
const int MAXN=1000+5;
char str[MAXN],pattern[MAXN];
int Next[MAXN];
int cnt;
void getfail(char *p) {
	int j=1,k=0;
	Next[0]=0; Next[1]=0;
	while(p[j]) {
		if(p[j]==p[k]) {
			++k;
			++j;
			if(p[j]==p[k])
				Next[j]=Next[k]; 
			else
				Next[j]=k;
		}
		else if(k==0) {
			++j;
			Next[j]=0;
		}
		else	k=Next[k];
	}
}
int kmp(char *s,char *p){
    int last=-1;
    int plen=strlen(p);
    getfail(p);
    int j=0;
    for(int i=0;s[i];i++){
        while(j&amp;&amp;s[i]!=p[j])    j=Next[j];
        if(s[i]==p[j])    j++;
        if(j==plen){
            if(i-last&gt;=plen){
                cnt++;
                last=i;
            }
        }
    }
}
int main(){
    while(~scanf("%s",str)){
        if(str[0]=='#')    break;
        scanf("%s",pattern);
        cnt=0;
        kmp(str,pattern);
        printf("%d\n",cnt);
    }
}

hdu 3336，灵活运用Next数组，每个前缀至少出现一次，从前往后求和，Next[i]表示前i-1个字符所组成的字符串的最大前后缀匹配长度，即有多少个字串与前缀匹配，对字符串abcabacbabca，Next[4]=1($p[4]{=}^{\mathrm{\prime }}{b}^{\mathrm{\prime }}p[4]=\text{'}b\text{'}$)表示前缀a匹配成功,Next[5]=2表示前缀ab和后缀ab匹配成功,所以此时需要注意重复计数的问题:

思路： 每个前缀至少匹配一次（与自己匹配），有$lenlen$个前缀，$Next[i]=xNext[i]=x$，则前$ii$个长度($0\sim i-10\backslash sim\; i-1$)的子串中，有$xx$个前缀和后缀匹配，如果$next[i+1]=x+1next[i+1]=x+1$，前$xx$个匹配情况已经计算过了。

#include<bits stdc++.h>
using namespace std;
char str[200005];
int Next[200005];
int ans,t,n;
int getFail(char *p) {
    Next[0]=0;    Next[1]=0;
    for(int i=1;p[i];i++){
        int j=Next[i];
        while(j&amp;&amp;p[i]!=p[j])    j=Next[j];
        Next[i+1]=(p[i]==p[j])?j+1:0;
    }
}
int main() {
	scanf("%d",&amp;t);
	while(t--) {
		scanf("%d",&amp;n);
		scanf("%s",str);
		getFail(str);
		ans=n+Next[n];
		for(int i=2;i<n;++i) if(next[i]>0&amp;&amp;Next[i]+1!=Next[i+1])
			ans+=Next[i];
		printf("%d\n",ans%10007);
	}
}

hdu 2594

题意： 给两个字符串$s1\mathrm{、}s2s1、s2$，求$s1s1$的前缀与$s2s2$的后缀最长匹配长度，并输出匹配的子串。 思路： 把$s1\mathrm{、}s2s1、s2$拼接起来，然后得出$next[]next[]$数组，$next[len1]next[len1]$就是最长匹配长度，特判$next[len1]next[len1]$大于$s1s1$的长度，因为$s1s1$的前缀不可能比自己还长。

#include<bits stdc++.h>
using namespace std;
char str[100005];
int Next[100005];
int ans,len,len1;
int getFail(char *p) {
    Next[0]=0;    Next[1]=0;
    for(int i=1;p[i];i++){
        int j=Next[i];
        while(j&amp;&amp;p[i]!=p[j])    j=Next[j];
        Next[i+1]=(p[i]==p[j])?j+1:0;
    }
}
int main() {
    while(~scanf("%s",str)) {
    	len=strlen(str);
        scanf("%s",str+len);
        getFail(str);
        len1=strlen(str);
        ans=Next[len1];
        if(!ans)    puts("0");
        else {
        	len1=strlen(str)-len;
        	len=min(len,len1);
        	ans=min(len,ans);
            str[ans]='\0';
            printf("%s %d\n",str,ans);
        }
    }
}
```</bits></n;++i)></bits></bits></plen;i++){></bits>