KMP和EXKMP（Z函数）

KMP

单个字符串匹配算法。

这个算法的思想也影响到了后面很多的算法，如SAM，ACAM，等等。

算法本身的核心思想是根据子串的next数组进行失配时的优化跳转策略，算是某种意义上的贪心吧。

这里放上一张图来理解求解next数组的过程。

代码部分相对简单也没有太多可以修改的地方
下面连个函数中p数组是next数组，pre用于预处理next数组，kmp函数用于匹配。

void pre()//预处理next数组
{
    
    p[1]=0;int j=0;
    for(int i=1;i<m;i++)
    {
    
        while(j>0&&s2[j+1]!=s2[i+1])
            j=p[j];
        if(s2[j+1]==s2[i+1])
            j++;
        p[i+1]=j;
    }
}
void kmp()
{
    
    int ans=0,j=0;
    for(int i=0;i<n;i++)
    {
    
        while(j>0&&s2[j+1]!=s1[i+1])
            j=p[j];
        if(s2[j+1]==s1[i+1]) j++;
        if(j==m)
        {
    
		    //ans++; 匹配数量确认
            printf("%d\n",i-m);
            j=p[j];
            //j=0 不可重叠确认
        }
    }
}

EXKMP

能够线性复杂度求出一个字符串a和自身所有后缀的LCP（Z函数）。也能求出和别的字符串所有后缀的LCP（EXKMP过程）。

P5410 【模板】扩展 KMP（Z 函数）

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e7+7;
int n,m,z[N],p[N];//b的z数组，z[i]代表以i为起始的后缀和b的LCP，匹配串的P数组，p[i]代表
char a[N],b[N];
void get_Z(char *s,int n)
{
    
	for(int i=1;i<=n;i++)
        z[i]=0;
	z[1]=n;
	for(int i=2,l=0,r=0;i<=n;i++)
    {
    
		if(i<=r)
		    z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])
            ++z[i];
		if(i+z[i]-1>r){
    
		    l=i;
		    r=i+z[i]-1;
		}
	}
}
void exkmp(char *s,int n,char *t,int m)
{
    
	get_Z(t,m);
	for(int i = 1;i<=n;i++)
        p[i]=0;
	for (int i=1,l=0,r=0;i<=n;i++)
    {
    
		if(i<=r)
		p[i]=min(z[i-l+1],r-i+1);
		while(i+p[i]<=n&&s[i+p[i]]==t[p[i]+1])
		 ++p[i];
		if(i+p[i]-1>r)
		{
    
		    l=i;
		    r=i+p[i]-1;
		}
	}
}
signed main()
{
    
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
	cin>>(a+1);
	cin>>(b+1);
	n=strlen(a+1);
	m=strlen(b+1);
	exkmp(a,n,b,m);
	int ans=0;
	for(int i=1;i<=m;i++)
        ans^=i*(z[i]+1);
	cout<<ans<<endl;
	ans=0;
	for(int i=1;i<=n;i++)
        ans^=1ll*i*(p[i]+1);
	cout<<ans<<endl;
	return 0;
}