[HEOI2015]最短不公共子串 - A-Failure的博客

题目

题目描述

在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。

一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。

一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。

下面，给两个小写字母串A，B，请你计算：

(1) A的一个最短的子串，它不是B的子串

(2) A的一个最短的子串，它不是B的子序列

(3) A的一个最短的子序列，它不是B的子串

(4) A的一个最短的子序列，它不是B的子序列

输入输出格式

输入格式：

有两行，每行一个小写字母组成的字符串，分别代表A和B。

输出格式：

输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1.

输入输出样例

输入样例#1：

aabbcc
abcabc

输出样例#1：

输入样例#2：

aabbcc
aabbcc

输出样例#2：

-1
-1
2
-1

说明

对于20%的数据，A和B的长度都不超过20

对于50%的数据，A和B的长度都不超过500

对于100%的数据，A和B的长度都不超过2000

题解

1.直接在$B$的$SAM$上跑即可

2.$O(n^2)$处理出$B$每个位置下一个字符$x$的位置，然后从左到右贪心即可

3.$f_i$表示$B$的$SAM$上以节点$i$结尾的最短长度，从左到右枚举$A$的字符，依次更新$f$，相当于一个递推的过程

4.$f_i$表示$B$字符串上以$i$位置结尾的最短长度，跟问题$3$一样处理，只是倒着枚举$SAM$节点

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e3+5;
int n,_n;
char a[MAX],b[MAX];
struct SAM{
	int l,r,L;
	int len[MAX],fa[MAX],f[MAX];
	int son[MAX][26],nxt[MAX][26];
	SAM() {l=r=1;}
	void ins(int x)
	{
		int tt=r;
		len[r=++l]=++L;
		for(;tt&&!son[tt][x];tt=fa[tt])
		  son[tt][x]=r;
		if(!tt) return void(fa[r]=1);
		int qwq=son[tt][x];
		if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
		len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l;
		for(int i=0;i<26;++i)
		  son[l][i]=son[qwq][i];
		for(int i=tt;son[i][x]==qwq;i=fa[i])
		  son[i][x]=l;
	}
	void Solve()
	{
		int ans=1e9;
		for(int i=1,N;i<=n;++i)
		  {
		  	N=min(i+ans-1,n);
		  	for(int j=i,x=1;j<=N;++j)
		  	  {
		  	  	x=son[x][a[j]-'a'];
		  	  	if(!x) {ans=j-i+1;break;}
			  }
		  }
		printf("%d\n",ans==1e9?-1:ans);
	}
	void Solve_()
	{
		int ans=1e9;
		for(int i=0;i<_n;++i)
		  for(int j=i+1;j<=_n;++j)
		    if(!nxt[i][b[j]-'a']) nxt[i][b[j]-'a']=j;
		for(int i=1,N;i<=n;++i)
		  {
		  	N=min(i+ans-1,n);
		  	for(int j=i,x=0;j<=N;++j)
		  	  {
		  	  	x=nxt[x][a[j]-'a'];
		  	  	if(!x) {ans=j-i+1;break;}
			  }
		  }
		printf("%d\n",ans==1e9?-1:ans);
	}
	void Solve__()
	{
		int ans=1e6;
		memset(f,1,sizeof(f));
		f[1]=0;
		for(int i=1;i<=n;++i)
		  for(int j=1,x;j<=l;++j)
		    {
		    	x=son[j][a[i]-'a'];
		    	if(!x) ans=min(ans,f[j]+1);
		    	else f[x]=min(f[x],f[j]+1);
			}
		printf("%d\n",ans==1e6?-1:ans);
	}
	void Solve___()
	{
		int ans=1e6;
		memset(f,1,sizeof(f));
		f[0]=0;
		for(int i=1;i<=n;++i)
		  for(int j=_n,x;j>=0;--j)
		    {
		    	x=nxt[j][a[i]-'a'];
		    	if(!x) ans=min(ans,f[j]+1);
		    	else f[x]=min(f[x],f[j]+1);
			}
		printf("%d\n",ans==1e6?-1:ans);
	}
}_S;
int main()
{
	scanf("%s%s",a+1,b+1),n=strlen(a+1),_n=strlen(b+1);
	for(int i=1;i<=_n;++i)
	  _S.ins(b[i]-'a');
	return _S.Solve(),_S.Solve_(),_S.Solve__(),_S.Solve___(),0;
}

题目