bzoj 4032 最短不公共子串

Posted on | Views:

$SAM$ + 子序列自动机.

对于两个串,建出它们各自的后缀自动机和子序列自动机.

对于每种询问,就将两个对应的自动机取出来,跑 $bfs$ .

某个状态 $(a,b)$ ,接受了一个字符 $c$ 后,若 $A$ 的自动机上有出边,而 $B$ 没有,则当前状态的深度 $+1$ 就是答案.

若两者都有出边,就将转移到的新的状态入队.

记忆化一下,时间复杂度 $O(n^2|S|)$ ,其中 $S$ 表示字符集大小.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=4e3+10,S=26;
struct AutoMaton
{
	int ch[MAXN][S],fa[MAXN],len[MAXN],idx,lst;
	int st;
	AutoMaton(){idx=lst=1;}
	void init_seq(char *buf,int n)
	{
		st=0;
		int cur[S]={0};
		for(int i=n;i>=1;--i)
		{
			memcpy(ch[i],cur,sizeof ch[i]);
			cur[buf[i]-'a']=i;
		}
		memcpy(ch[0],cur,sizeof ch[0]);
	}
	void Extend(int c)
	{
		int p=lst,np=++idx;
		lst=np;
		len[np]=len[p]+1;
		while(p && ch[p][c]==0)
			ch[p][c]=np,p=fa[p];
		if(p==0)
			fa[np]=1;
		else
		{
			int q=ch[p][c];
			if(len[q]==len[p]+1)
				fa[np]=q;
			else
			{
				int nq=++idx;
				len[nq]=len[p]+1;
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				memcpy(ch[nq],ch[q],sizeof ch[nq]);
				while(p && ch[p][c]==q)
					ch[p][c]=nq,p=fa[p];
			}
		}
	}
	void init_SAM(char *buf,int n)
	{
		st=1;
		for(int i=1;i<=n;++i)
		{
			int c=buf[i]-'a';
			Extend(c);
		}
	}
}A[2],B[2];
struct node
{
	int a,b,dep;
	node(int a=0,int b=0,int dep=0):a(a),b(b),dep(dep) {}
};
queue<node> q;
bool vis[MAXN][MAXN];
int solve(const AutoMaton &A,const AutoMaton &B)
{
	while(!q.empty())
		q.pop();
	memset(vis,0,sizeof vis);
	q.push(node(A.st,B.st,0));
	vis[A.st][B.st]=1;
	while(!q.empty())
	{
		node tmp=q.front();
		q.pop();
		int a=tmp.a,b=tmp.b;
		for(int i=0;i<S;++i)
		{
			if(A.ch[a][i] && !B.ch[b][i])
				return tmp.dep+1;
			else if(A.ch[a][i] && B.ch[b][i] && !vis[A.ch[a][i]][B.ch[b][i]])
			{
				q.push(node(A.ch[a][i],B.ch[b][i],tmp.dep+1));
				vis[A.ch[a][i]][B.ch[b][i]]=1;
			}	
		}
	}
	return -1;
}
char buf[MAXN];
int main()
{
	scanf("%s",buf+1);
	int n=strlen(buf+1);
	A[0].init_SAM(buf,n);
	A[1].init_seq(buf,n);
	scanf("%s",buf+1);
	n=strlen(buf+1);
	B[0].init_SAM(buf,n);
	B[1].init_seq(buf,n);
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			printf("%d\n",solve(A[i],B[j]));
	return 0;
}