【BZOJ4032】[HEOI2015]最短不公共子串（后缀自动机，序列自动机）

题面

BZOJ

洛谷

题解

数据范围很小，直接暴力构建后缀自动机和序列自动机，然后直接在两个自动机上进行\(bfs\)，找到的第一个不同时存在的节点就直接输出就好了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define MAX 4040

struct SAM

{

	struct Node{int son[26],ff,len;}t[MAX];

	int tot,last;void init(){tot=last=1;}

	void extend(int c)

	{

		int p=last,np=++tot;last=tot;

		t[np].len=t[p].len+1;

		while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;

		if(!p)t[np].ff=1;

		else

		{

			int q=t[p].son[c];

			if(t[q].len==t[p].len+1)t[np].ff=q;

			else

			{

				int nq=++tot;

				t[nq]=t[q];t[nq].len=t[p].len+1;

				t[q].ff=t[np].ff=nq;

				while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;

			}

		}

	}

}A,B;

struct SQAM

{

	struct Node{int son[26];}t[MAX];

	int lst[26],pre[MAX],tot,last;

	void init(){tot=last=1;for(int i=0;i<26;++i)lst[i]=1;}

	void extend(int c)

	{

		int p=lst[c],np=++tot;

		pre[np]=p;

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

			for(int j=lst[i];j&&!t[j].son[c];j=pre[j])

				t[j].son[c]=np;

		lst[c]=np;

	}

}AA,BB;

char SA[MAX],SB[MAX];

int na,nb;

struct Node{int len,a,b;};

bool vis[MAX][MAX];

int bfs1(SAM &A,SAM &B)

{

	queue<Node> Q;Q.push((Node){0,1,1});

	memset(vis,0,sizeof(vis));vis[1][1]=true;

	while(!Q.empty())

	{

		Node p=Q.front();Q.pop();

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

		{

			int x=A.t[p.a].son[i];

			int y=B.t[p.b].son[i];

			if(x&&y)

			{

				if(vis[x][y])continue;

				vis[x][y]=true;Q.push((Node){p.len+1,x,y});

			}

			if(x&&!y)return p.len+1;

		}

	}

	return -1;

}

int bfs2(SAM &A,SQAM &B)

{

	queue<Node> Q;Q.push((Node){0,1,1});

	memset(vis,0,sizeof(vis));vis[1][1]=true;

	while(!Q.empty())

	{

		Node p=Q.front();Q.pop();

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

		{

			int x=A.t[p.a].son[i];

			int y=B.t[p.b].son[i];

			if(x&&y)

			{

				if(vis[x][y])continue;

				vis[x][y]=true;Q.push((Node){p.len+1,x,y});

			}

			if(x&&!y)return p.len+1;

		}

	}

	return -1;

}

int bfs3(SQAM &A,SAM &B)

{

	queue<Node> Q;Q.push((Node){0,1,1});

	memset(vis,0,sizeof(vis));vis[1][1]=true;

	while(!Q.empty())

	{

		Node p=Q.front();Q.pop();

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

		{

			int x=A.t[p.a].son[i];

			int y=B.t[p.b].son[i];

			if(x&&y)

			{

				if(vis[x][y])continue;

				vis[x][y]=true;Q.push((Node){p.len+1,x,y});

			}

			if(x&&!y)return p.len+1;

		}

	}

	return -1;

}

int bfs4(SQAM &A,SQAM &B)

{

	queue<Node> Q;Q.push((Node){0,1,1});

	memset(vis,0,sizeof(vis));vis[1][1]=true;

	while(!Q.empty())

	{

		Node p=Q.front();Q.pop();

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

		{

			int x=A.t[p.a].son[i];

			int y=B.t[p.b].son[i];

			if(x&&y)

			{

				if(vis[x][y])continue;

				vis[x][y]=true;Q.push((Node){p.len+1,x,y});

			}

			if(x&&!y)return p.len+1;

		}

	}

	return -1;

}

int main()

{

	scanf("%s%s",SA+1,SB+1);

	na=strlen(SA+1);nb=strlen(SB+1);

	A.init();B.init();AA.init();BB.init();

	for(int i=1;i<=na;++i)A.extend(SA[i]-97);

	for(int i=1;i<=nb;++i)B.extend(SB[i]-97);

	for(int i=1;i<=na;++i)AA.extend(SA[i]-97);

	for(int i=1;i<=nb;++i)BB.extend(SB[i]-97);

	printf("%d\n%d\n%d\n%d\n",bfs1(A,B),bfs2(A,BB),bfs3(AA,B),bfs4(AA,BB));

	return 0;

}