bzoj 2946 公共串

Posted on | Views:

$SAM$ 解决多个串的最长公共子串.

  • $SAM$.
  • 显然可以 二分 + $hash$ 做,时间复杂度 $O(logL\cdot L \cdot n)$.
  • 考虑 $SAM$ 的做法.对第一个串建个 $SAM$ ,然后每读入一个新串就把它放在自动机上匹配.
  • 匹配时维护每个状态能与每个串都匹配的最大长度.最后的答案就是所有状态能匹配长度的最大值.
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
    ll 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 Siz=26,MAXN=4e3+10;
char buf[MAXN];
int L,n;
struct SuffixAutoMation
{
	int idx,lst;
	int fa[MAXN],ch[MAXN][Siz];
	int len[MAXN],siz[MAXN];
	int A[MAXN],t[MAXN];
	int mxl[MAXN],res[MAXN];
	SuffixAutoMation(){idx=lst=1;}
	void Extend(int c)
	{
		int p=lst,np=++idx;
		lst=np;
		res[np]=len[np]=len[p]+1;
		siz[np]=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;
				res[nq]=len[nq]=len[p]+1;
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				memcpy(ch[nq],ch[q],sizeof ch[q]);
				while(p && ch[p][c]==q)
					ch[p][c]=nq,p=fa[p];
			}
		}
	}
	void topsort()
	{
		for(int i=1;i<=idx;++i)
			++t[len[i]];
		for(int i=1;i<=idx;++i)
			t[i]+=t[i-1];
		for(int i=1;i<=idx;++i)
			A[t[len[i]]--]=i;
	}
	void solve()
	{
		scanf("%s",buf+1);
		memset(mxl,0,sizeof mxl);
		L=strlen(buf+1);
		int p=1,tmp=0;
		for(int i=1;i<=L;++i)
		{
			int c=buf[i]-'a';
			while(p && ch[p][c]==0)
				p=fa[p];
			if(p==0)
				p=1,tmp=0;
			else
			{
				tmp=min(tmp,len[p])+1;
				p=ch[p][c];
			}
			mxl[p]=max(mxl[p],tmp);
		}
		for(int i=idx;i>=1;--i)
		{
			int u=A[i];
			mxl[fa[u]]=max(mxl[fa[u]],mxl[u]);
		}
		for(int i=1;i<=idx;++i)
			res[i]=min(res[i],mxl[i]);
	}
	void pr()
	{
		int ans=0;
		for(int i=1;i<=idx;++i)
			ans=max(ans,res[i]);
		cout<<ans<<endl;
	}
}SAM;
int main()
{
	n=read();
	scanf("%s",buf+1);
	L=strlen(buf+1);
	for(int i=1;i<=L;++i)
		SAM.Extend(buf[i]-'a');
	SAM.topsort();
	for(int i=1;i<n;++i)
		SAM.solve();
	SAM.pr();
    return 0;
}