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

做法千万万

对串$A\#B$建立$SAM$

如果是插入第一个串产生的节点标记为$1$,插入第二个串产生的节点标记为$2$

维护一下每个$endpos$出现几次,发现答案一定是那些出现次数为$2$的节点

因为只在两个串中出现一次,而且一定不包含$\#$,包含$\#$的子串只会出现一次

那如何判断这个$endpos$类是在一个串中出现两次,还是分别在两个串中出现一次呢

如果是分别在两个串中出现一次,那这个节点一定是由串$A$新建的

然后插入串$B$的时候,也出现过这个$endpos$,所以会把后缀链接指向这个$endpos$

那我们只需要拓扑排序推标记即可

#include 
   
    using namespace std;const int maxn = 2e5+10;char a[maxn],b[maxn];int zi[maxn][33],len[maxn],fa[maxn],mark[maxn],siz[maxn],ed=1,id=1;void add(int c,int x){
   	int p = ed, np = ++id; ed = id;	mark[np] = x, len[np] = len[p]+1; siz[np] = 1;	for( ; p && !zi[p][c]; p = fa[p] )	zi[p][c] = np;	if( p==0 )	fa[np] = 1;	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] );			fa[nq] = fa[q], len[nq] = len[p]+1, mark[nq] = mark[q];			fa[np] = fa[q] = nq;			for( ;p&&zi[p][c]==q;p=fa[p] )	zi[p][c] = nq;		}	}}int c[maxn],rk[maxn],ans=1e9;void chiken_sort(){
   	for(int i=1;i<=id;i++)	c[len[i]]++;	for(int i=1;i<=id;i++)	c[i] += c[i-1];	for(int i=1;i<=id;i++)	rk[c[len[i]]--] = i;	for(int i=id;i>=1;i--)	{
   		int u = rk[i];		siz[fa[u]] += siz[u]; mark[fa[u]] |= mark[u];		if( siz[u]==2&&mark[u]==3 )	ans = min( ans,len[fa[u]]+1 );	}}int main(){
   	cin >> ( a+1 ) >> ( b+1 );	int len1 = strlen( a+1 ), len2 = strlen( b+1 );	for(int i=1;i<=len1;i++)	add( a[i]-'a',1 );	add( 26,1 );	for(int i=1;i<=len2;i++)	add( b[i]-'a',2 );	chiken_sort();	if( ans==1e9 )	cout << -1;	else	cout << ans;}
   

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