本文共 1579 字，大约阅读时间需要 5 分钟。

因为是求每个前缀,所以后缀数组肯定不行,考虑构建$SAM$

求每个前缀的两两后缀的$lcp$的$mex$

对于一个确定的$SAM$,任意两个节点的$LCA$就是他们的最长公共后缀

我们可以求两两前缀的公共后缀,但是却求不了两两后缀的公共前缀

但其实两者在数值上是等价的

设想一个节点有两个儿子,说明可以作为两个后缀的$lcs$

设这个节点长度为$x$,说明$[1,x]$都是存在的,因为可以把两个后缀同时削减一些长度

所以我们增量构造时,每次新建前缀节点$np$

$fa[np]$拥有儿子节点$np$,而且$fa[np]$的$endpos$和$np$不同

说明$fa[np]$一定存在其他的儿子节点,也就是可以作为$LCA$

所以一直对$len[fa[np]]$取$max$即可

注意,如果都是一串相同的字母比如$aaaa$,$LCP$的值不存在$0$,所以是输出$0$

这个就是看根节点是否有两个或以上的节点就好了

#include 
   
    using namespace std;const int maxn = 2e6+10;int t,n,ans;char a[maxn];int zi[maxn][30],fa[maxn],len[maxn],ed=1,id=1,son;void insert(int c){
   	int p = ed, np = ++id; ed = id;	len[np] = len[p]+1;	for( ;p&&!zi[p][c];p=fa[p] )	zi[p][c] = np;	if( !p )	fa[np] = 1,son++;	else	{
   		int q = zi[p][c];		if( len[q]==len[p]+1 )	fa[np] = q;		else		{
   			int nq = ++id;			memcpy( zi[nq],zi[q],sizeof zi[nq] );			len[nq] = len[p]+1, fa[nq] = fa[q];			fa[np] = fa[q] = nq;			for( ;p&&zi[p][c]==q;p=fa[p] )	zi[p][c] = nq;		}	}	ans = max( ans,len[fa[np]] );}int main(){
   	cin >> t;	while( t-- )	{
   		scanf("%s",a+1); n = strlen( a+1 );		printf("0 ");		insert( a[1]-'a' );		for(int i=2;i<=n;i++)		{
   			insert( a[i]-'a' );			if( son>=2 )	printf("%d ",ans+1);			else	printf("%d ",0);		}		printf("\n");		for(int i=1;i<=id;i++)		{
   			memset( zi[i],0,sizeof zi[i] );			len[i] = fa[i] = 0;		}		ed = id = 1; ans = son = 0;	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114413324 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！