Description
求多个字符串的最长公共子串。
Solution
选出最短串 S,对其建立 SAM,将其它所有串依次扔到上面跑,下面设当前用串 T
跑的时候,维护当前匹配长度 tmp 和当前位置 p
对自动机的每个结点,维护一个权值 now[i]
如果能走 trans 边就走,tmp++
否则,p=link[p], tmp=maxlen[p]
走过每一步后,now[p]=max(now[p],tmp)
跑完串 T 后,对 now[] 沿着 link 按照拓扑逆序上传,即 now[link[p]]=max(now[link[p]],now[p])
对每个自动机上的结点,我们维护 ans[p] 为对于所有 T 得到的 now[p] 的最小值
那么 max(ans[p]) 就是答案
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 200005;
struct Suffix_Automata {
int maxlen[Maxn], trans[Maxn][26], link[Maxn], Size, Last;
int t[Maxn], a[Maxn], cnt[Maxn], f[Maxn], now[Maxn], ans[Maxn];
Suffix_Automata() { Size = Last = 1; memset(ans,0x3f,sizeof ans);}
inline void Extend(int id) {
int cur = (++ Size), p;
maxlen[cur] = maxlen[Last] + 1;
cnt[cur] = 1;
for (p = Last; p && !trans[p][id]; p = link[p]) trans[p][id] = cur;
if (!p) link[cur] = 1;
else {
int q = trans[p][id];
if (maxlen[q] == maxlen[p] + 1) link[cur] = q;
else {
int clone = (++ Size);
maxlen[clone] = maxlen[p] + 1;
for(int i=0;i<26;i++) trans[clone][i] = trans[q][i];
link[clone] = link[q];
for (; p && trans[p][id] == q; p = link[p]) trans[p][id] = clone;
link[cur] = link[q] = clone;
}
}
Last = cur;
}
void rsort() {
memset(t, 0, sizeof t);
for(int i=1; i<=Size; i++) t[maxlen[i]]++;
for(int i=1; i<=Size; i++) t[i]+=t[i-1];
for(int i=1; i<=Size; i++) a[t[maxlen[i]]--]=i;
}
void solve(string str) {
int p=1, tmp=0;
memset(now,0,sizeof now);
for(int i=0;i<str.length();i++) {
while(p>1 && trans[p][str[i]-'a']==0) p=link[p], tmp=maxlen[p];
if(trans[p][str[i]-'a']) ++tmp, p=trans[p][str[i]-'a'];
now[p] = max(now[p], tmp);
}
for(int i=Size;i>=1;--i) {
int p=a[i];
now[link[p]]=max(now[link[p]],min(maxlen[link[p]],now[p]));
}
for(int i=1;i<=Size;i++) {
ans[i]=min(ans[i],now[i]);
}
}
int getans() {
return *max_element(ans+1,ans+Size+1);
}
} sam;
int main() {
ios::sync_with_stdio(false);
int n;
cin>>n;
string s[26];
for(int i=1;i<=n;i++) {
cin>>s[i];
}
int id=1;
for(int i=2;i<=n;i++) {
if(s[i].length() < s[id].length()) id=i;
}
string &str = s[id];
for(int i=0;i<str.length();i++)
sam.Extend(str[i]-'a');
sam.rsort();
for(int i=1;i<=n;i++) if(i!=id) {
sam.solve(s[i]);
}
cout<<sam.getans();
}