exkmp

与 kmp 思想相似因而也被称作扩展kmp算法，用于在 \(O(n+m)\) 的复杂度内求解长度为 \(n\) 的字符串 \(S\) 的所有后缀与长度为 \(m\) 的字符串 \(T\) 的最长公共前缀。

\(next\)

对模式串 \(T\) 构建 \(next\) 数组，其中 \(nxt[i]\) 表示 \(T_{i\sim n}\) 与 \(T\) 的最长公共前缀长度。

对于 \(\forall x \in [2,n]\) ，假设 \(\forall i\in [2,x)\ nxt[i]\) 都已求出，则求解 \(nxt[x]\) 的过程如下：

令 \(nxt[i]+i-1\) 的最大值为 \(p=k+nxt[k]-1\)，即目前匹配到的最长前缀。

懒得画图，直接说结论吧，以后看博客复习就 就 再手推一遍（

令 \(L=nxt[x-k]\)

若 \(x+L\leq p\) ， \(nxt[x]=L\)

否则从 \(p-x+1\) 和 \(p+1\) 开始暴力匹配（

\(extend\)

与 \(nxt\) 数组的构建方式一致。

#include 
using namespace std;

long long read()
{
	long long res=0,p=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')p=-1; ch=getchar();}
	while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();
	return res*p;
}

const int maxn=2e7+10;

char s[maxn],t[maxn];
int nxt[maxn],ext[maxn],n,m,len;
long long ans=0,k,p,L;

inline int getPn(int id) {return id+nxt[id]-1;}
inline int getPe(int id) {return id+ext[id]-1;}

void gNxt()
{
	nxt[0]=n,k=1;
	for(int i=1;i>t>>s;
	n=strlen(s),m=strlen(t),len=min(n,m);
	gNxt(),gExt();
	for(int i=0;i