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

题意

给出$n$个字符串,求只在串$1$中出现的最短且字典序最小的子串。

设第一个串长$len$

把$n$个串插入分隔符串起来求后缀数组,设新串总长度为$l$

枚举$i$满足$s{a}_i<=len$,说明$s{a}_i$这个后缀起始于串$1$

设$i$左边第一个不属于串$1$的后缀为$s{a}_{left}$,设$i$右边第一个不属于串$1$的后缀为$s{a}_{right}$

那么求出$ans=max(LCP(s{a}_{left},s{a}_i),LCP(s{a}_{right},s{a}_i))+1$

也就是说,如果以$s{a}_i$位置开头的子串,长度至少为$ans$才能保证不在其他串中出现过

所以$len-s{a}_i+1$至少需要大于等于$ans$,否则这个位置开头的子串都不合法

由于$ans$已经满足最小,而且我们是根据后缀数组的$sa$数组字典序小到大枚举

所以一定是长度最小且字典序最小的

#include 
   
    using namespace std;const int maxn = 2e6+10;char b[maxn],s[maxn];int a[maxn],id[maxn];int sa[maxn],rk[maxn],height[maxn],c[maxn],x[maxn],y[maxn],st[maxn][22];int n,m,casenum;void SA(int n){
   	m = n+'z';	for(int i=0;i<=m;i++)	c[i] = 0;	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-1]]==y[sa[i]]&&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;	}}void ST(int n){
   	for(int i=1;i<=n;i++)	st[i][0] = height[i];	for(int i=1;i<=20;i++)	for(int j=1;j+(1<
    
     <=n;j++)		st[j][i] = min( st[j][i-1],st[j+(1<<(i-1))][i-1] );}int get(int l,int r){
   	int k = log2(r-l+1);	return min( st[l][k],st[r-(1<
     
      fi )	le[i] = i;	}	for(int i=n;i>=1;i--)	{
   		re[i] = re[i+1];		if( sa[i]>fi )	re[i] = i;	}	int ans = 1e9, index = 0;	for(int i=1;i<=n;i++)	{
   		if( sa[i]>fi )	continue; 		int flag = 0;//最长 		if( le[i]!=0 )	flag = get(le[i]+1,i)+1; 		if( re[i]!=0 )	flag = max( flag,get(i+1,re[i])+1 );		if( fi-sa[i]+1>=flag && flag
      
       > t;	while( t-- )	{
   		scanf("%d%s",&n,b+1);		int l = strlen( b+1 );		for(int i=1;i<=l;i++)	a[i] = b[i]-'a';		for(int i=2;i<=n;i++)		{
   			scanf("%s",s+1 ); int m = strlen( s+1 );			a[++l] = i+'z';//作为分隔符 			for(int j=1;j<=m;j++)	a[++l] = s[j]-'a';		}		SA(l); ST(l);		solve(l);		init(l);	}}
      
     
    
   

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