分析

这道题有个\(O(n)\)的后缀自动机做法，感觉很好理解就在这说一下。

先对\(s1\)和\(s2\)求最长公共子串，对于\(s2\)的每一个下标\(i\)，求一个\(f[i]\)表示以\(s2[i]\)结尾的最长匹配长度。

KMP求出\(s3\)在\(s2\)上的所有结束位置，然后扫一遍\(s2\)统计答案，很简单。

代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

const int MAXN=50005;

int len1,len2,len3,las,tot,maxlen[MAXN],nxt[MAXN];

char s1[MAXN],s2[MAXN],s3[MAXN];

bool mat[MAXN];

struct sam{

	int fa,to[26];

	int len;

}a[MAXN<<1];

void extend(int c){

	int p=las,np=++tot;las=np,a[np].len=a[p].len+1;

	while(p&&!a[p].to[c]) a[p].to[c]=np,p=a[p].fa;

	if(!p){a[np].fa=1;return;}

	int q=a[p].to[c];

	if(a[p].len+1==a[q].len){a[np].fa=q;return;}

	int nq=++tot;a[nq]=a[q],a[nq].len=a[p].len+1,a[np].fa=a[q].fa=nq;

	while(p&&a[p].to[c]==q) a[p].to[c]=nq,p=a[p].fa;

}

void kmp(){

	nxt[1]=0;

	for(register int i=2,j=0;i<=len3;++i){

		while(j&&s3[i]!=s3[j+1]) j=nxt[j];

		if(s3[i]==s3[j+1]) ++j;

		nxt[i]=j;

	}

	for(register int i=1,j=0;i<=len2;++i){

		while(j&&s2[i]!=s3[j+1]) j=nxt[j];

		if(s2[i]==s3[j+1]) ++j;

		if(j==len3){

			mat[i]=true;

			j=nxt[j];

		}

	}

}

void solve(){

	int now=1,cur=0;

	rin(i,1,len2){

		while(now&&!a[now].to[s2[i]-'a']) now=a[now].fa,cur=a[now].len;

		if(!now){now=1,cur=0;continue;}

		now=a[now].to[s2[i]-'a'],++cur;

		maxlen[i]=cur;

	}

}

int main(){

	scanf("%s",s1+1);

	getchar();

	scanf("%s",s2+1);

	getchar();

	scanf("%s",s3+1);

	len1=strlen(s1+1);

	len2=strlen(s2+1);

	len3=strlen(s3+1);

	las=tot=1;

	rin(i,1,len1) extend(s1[i]-'a');

	kmp();

	solve();

	int ans=0,lim=1e9;

	rin(i,1,len2){

		if(mat[i]) lim=len3-1;

		ans=std::max(ans,std::min(maxlen[i],lim++));

	}

	printf("%d\n",ans);

	return 0;

}