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

求出$SA$数组

$height[i]$表示排名为$i-1$的后缀和$i$的后缀的$lcp$

考虑$sa[i-2]sa[i-1]sa[i]sa[i+1]$这四个后缀依靠

$height[i-1]height[i]height[i+1]$联系起来

其中$min(height[i-1],height[i],height[i+1])$是四个后缀公共的$lcp$

考虑最后分别出现在两个串唯一一次的串$s$

一定是$sa[i-1]$的前缀是$s$,而且$sa[i]$的前缀也是$s$

而且$sa[i-2]$的前缀不是$s$,而且$sa[i+1]$的前缀不是$s$

这相当于

$height[i]>height[i-1]\&\&height[i]>height[i+1]$

这样,$max(height[i-1],height[i+1])+1$往后的长度都只在$sa[i-1]$和$sa[i]$中出现过

此时只需要确认$sa[i-1]$和$sa[i]$是来自两个不同的串即可

#include 
   
    using namespace std;const int maxn = 2e5+10;int c[maxn],rk[maxn],sa[maxn],x[maxn],y[maxn],height[maxn],m;char a[maxn],b[maxn];void SA(int n){
   	m = 500;	for(int i=1;i<=n;i++)	c[x[i]=a[i]]++;	for(int i=1;i<=m;i++)	c[i] += c[i-1];	for(int i=n;i>=1;i--)	sa[c[x[i]]--] = i;	for(int k=1;k<=n;k<<=1 )	{
   		int num = 0;		for(int i=n-k+1;i<=n;i++)	y[++num] = i;		for(int i=1;i<=n;i++)	if( sa[i]>k )	y[++num] = sa[i]-k;		for(int i=0;i<=m;i++)	c[i] = 0;		for(int i=1;i<=n;i++)	c[x[i]]++;		for(int i=1;i<=m;i++)	c[i] += c[i-1];		for(int i=n;i>=1;i--)	sa[c[x[y[i]]]--] = y[i], y[i] = 0;		swap(x,y);		num = 1, x[sa[1]] = 1;		for(int i=2;i<=n;i++)			x[sa[i]] = ( y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] )?num:++num;		if( num==n )	break;		m = num;	}	for(int i=1;i<=n;i++)	rk[sa[i]] = i;	for(int i=1,k=0;i<=n;i++)	{
   		if( rk[i]==1 )	continue;		int j = sa[rk[i]-1];		if( k )	k--;		while( i+k<=n&&j+k<=n&&a[i+k]==a[j+k] )	k++;		height[rk[i]] = k;	}}int main(){
   	cin >> ( a+1 ) >> ( b+1 );	int len1 = strlen( a+1 ), len2 = strlen( b+1 );	a[len1+1] = '#';	for(int i=1;i<=len2;i++)	a[i+1+len1] = b[i]; 	SA(len1+1+len2);	int ans = 1e9;	for(int i=2;i<=len1+1+len2;i++)	{
   		if( sa[i-1]<=len1&&sa[i]<=len1 )	continue;		if( sa[i-1]>len1+1&&sa[i]>len1+1 )	continue;//需要来自不同的串		if( height[i]>height[i-1]&&height[i]>height[i+1] )			ans = min( ans,max(height[i-1],height[i+1])+1 ); 	}	if( ans==1e9 )	ans = -1;	cout << ans;}
   

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