bzoj 4032: [HEOI2015]最短不公共子串【dp+SAM】

第一、二问：

就是最小的最长公共长度+1，设f[i][j]为a匹配到i，b匹配到j，第一问的转移是f[i][j]=(a[i]b[j]?f[i-1][j-1]+1:0)，第二问的转移是f[i][j]=(a[i]b[j]?f[i-1][j-1]+1:f[i][j-1])，注意这里更新最小公共长度的时候，如果f[i][j]==i就不能更新，因为不能从前面随便新加的字符，后面加的不能保证不相等

第三问：

对b串建SAM，设g[i]为匹配到SAM上点i时的最短长度，然后枚举a的字符，如果能转移就转移，否则用失配位置更新答案

第四问：

同上，不用SAM，设c[i][j]为b串位置i后面第一个字符j的位置，当成SAM的ch转移，然后dp同上

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=4005;

int n,m,f[N][N],ans,ch[N][26],fa[N],tot=1,cur=1,la,dis[N],g[N],l[26],c[N][26];

char a[N],b[N];

void ins(int c,int id)

{

	la=cur;

	dis[cur=++tot]=id;

	int p=la;

	for(;p&&!ch[p][c];p=fa[p])

		ch[p][c]=cur;

	if(!p)

		fa[cur]=1;

	else

	{

		int q=ch[p][c];

		if(dis[q]==dis[p]+1)

			fa[cur]=q;

		else

		{

			int nq=++tot;

			dis[nq]=dis[p]+1;

			memcpy(ch[nq],ch[q],sizeof(ch[q]));

			fa[nq]=fa[q];

			fa[q]=fa[cur]=nq;

			for(;ch[p][c]==q;p=fa[p])

				ch[p][c]=nq;

		}

	}

}

int main()

{

	scanf("%s%s",a+1,b+1);

	n=strlen(a+1),m=strlen(b+1);

	ans=1e9;

	for(int i=1;i<=n;i++)

	{

		int mx=0;

		for(int j=1;j<=m;j++)

		{

			if(a[i]==b[j])

				f[i][j]=f[i-1][j-1]+1;

			mx=max(mx,f[i][j]);

		}

		if(mx!=i)

			ans=min(ans,mx+1);

	}

	printf("%d\n",ans>n?-1:ans);

	ans=1e9;

	memset(f,0,sizeof(f));

	for(int i=1;i<=n;i++)

	{

		int mx=0;

		for(int j=1;j<=m;j++)

		{

			if(a[i]==b[j])

				f[i][j]=f[i-1][j-1]+1;

			else

				f[i][j]=f[i][j-1];

			mx=max(mx,f[i][j]);

		}

		if(mx!=i)

			ans=min(ans,mx+1);

	}

	printf("%d\n",ans>n?-1:ans);

	for(int i=1;i<=m;i++)

		ins(b[i]-'a',i);

	ans=1e9;

	memset(g,0x3f,sizeof(g));

	g[1]=0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=tot;j++)

		{

			if(!ch[j][a[i]-'a'])

				ans=min(ans,g[j]+1);

			else

				g[ch[j][a[i]-'a']]=min(g[ch[j][a[i]-'a']],g[j]+1);

		}

	printf("%d\n",ans>n?-1:ans);

	for(int i=m;i>=0;i--)

	{

		for(int j=0;j<26;j++)

			c[i][j]=l[j];

		l[b[i]-'a']=i;

	}

	ans=1e9;

	memset(g,0x3f,sizeof(g));

	g[0]=0;

	for(int i=1;i<=n;i++)

		for(int j=m;j>=0;j--)

		{

			if(!c[j][a[i]-'a'])

				ans=min(ans,g[j]+1);

			else

				g[c[j][a[i]-'a']]=min(g[c[j][a[i]-'a']],g[j]+1);

		}

	printf("%d\n",ans>n?-1:ans);

	return 0;

}

巴特西

bzoj 4032: [HEOI2015]最短不公共子串【dp+SAM】

最新文章

热门文章