KMP模板及优化

博主链接

KMP模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=10001;
int next[maxn];
char s[maxn];
char p[maxn];
int cnt=0;
void prefix_next(int n){
	next[0]=0;
	int len=0;
	int i=1;
	while(i<n){
		if(p[i]==p[len]){
			len++;
			next[i]=len;
		}
		else {
			if(len>0){
				len=next[len-1];
			}
			else{
				next[i++]=len;
			}
		}
	}
	return;
}
void move_next(int n){
	for(int i=n-1;i>0;i--){
		next[i]=next[i-1];
	}
	next[0]=-1;
	return;
}
void kmp_search(){
	int n=strlen(p);
	int m=strlen(s);
	prefix_next(n);
	move_next(n);
	int i=0;
	int j=0;
	while(i<m){
		if(s[i]==p[j]&&j==n-1){
			printf("No.%d-->%d\n",++cnt,i-j);
			j=next[j];
		}
		if(s[i]==p[j]){
			i++;
			j++;
		}
		else{
			j=next[j];
			if(j==-1){
				i++;j++;
			}
		}
	}
	if(cnt==0)cout<<"NO FOUD"<<endl;
	return;
}
int main(){
	cin>>s;
	cin>>p;
	kmp_search();
}

KMP优化模板

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char s[1000005],t[200000];
int slen,tlen;
int nex[200000];//nex数组大小和短串一致
int ans,a,b,c,d,n,m;
inline void get_nex()
{
        int j=-1;//j初始化为-1
        for (int i=0;i<tlen;i++){
            while  (t[i]!=t[j+1] && j!=-1)//如果下一个不同，那么j就变成next[j]，注意next[j]是小于j的，无论j取任何值
			j=nex[j];//往前回溯
            if (t[i]==t[j+1] && i!=0) j++;//如果相同，j++
            nex[i]=j;//这个是把算的j的值（就是相同的最大前缀和最大后缀长）赋给next[i]
    	}
}
inline void kmp()
{
        int j=-1;
        for (int i=0;i<slen;i++){
            while  (s[i]!=t[j+1] && j!=-1) 
				j=nex[j];
            if (s[i]==t[j+1]) 
				j++;
            if (j==tlen-1)  
				ans++,j=nex[j];
        }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        ans=0;
        scanf("%s %s",t,s);
        slen=strlen(s);
        tlen=strlen(t);//这两个长度应该设为全局变量最开始时求出，不能用一次求一次
        get_nex();
        kmp();
        printf("%d\n",ans);
    }
}