@description@
求若干个仅由小写字母构成的字符串的最长公共子串。
input
有若干行。每行一个长度不超过 100000 的仅有小写字母构成的串。
保证串的个数不多于 10 个
output
输出最长公共子串。如果没有，输出 0。
sample input
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa
sample output
2
【话说仔细观察样例，再看看键盘，好像它的字母都是在键盘的第二行上】
【难不成是出题人用脸滚键盘滚出来的数据】
@solution@
【如果你不知道两个串的公共子串怎么弄，可以左转去我的这篇博客看看】
两个串的公共子串我们可以用后缀自动机来解决。那多个串呢？
答案是可以。考虑 A, B 的最长公共子串可能和 A, B, C 的最长公共子串没啥关系，我们先对某一个串建后缀自动机，再对于每一个结点去维护一个最长公共子串的长度，最后对每一个结点取 max。
怎么去维护呢？我们可以按照寻找两个串的公共子串的方法，把其他的串放在后缀自动机上跑，每一次跑都记录一个结点最优值，然后再沿着 fa 边更新父亲的最优值，最后和之前的最优值取 min（因为要求的是公共子串）。
@accepted code@
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
struct sam{
sam *ch[26], *fa; int mx;
sam *nxt; int ans, tmp;
}pl[2*MAXN + 5], *bin[MAXN + 5], *tcnt, *root, *lst;
void init() {
tcnt = root = lst = &pl[0];
for(int i=0;i<26;i++)
root->ch[i] = NULL;
root->fa = NULL, root->mx = 0;
}
sam *newnode() {
tcnt++;
for(int i=0;i<26;i++)
tcnt->ch[i] = NULL;
tcnt->fa = NULL, tcnt->mx = 0;
return tcnt;
}
void add_bin(sam *x) {
x->nxt = bin[x->mx];
bin[x->mx] = x;
}
void sam_extend(int x) {
sam *cur = newnode(), *p = lst;
cur->mx = lst->mx + 1, lst = cur;
add_bin(cur);
while( p && !p->ch[x] )
p->ch[x] = cur, p = p->fa;
if( !p )
cur->fa = root;
else {
sam *q = p->ch[x];
if( p->mx + 1 == q->mx )
cur->fa = q;
else {
sam *cne = newnode();
(*cne) = (*q), cne->mx = p->mx + 1;
q->fa = cur->fa = cne;
add_bin(cne);
while( p && p->ch[x] == q )
p->ch[x] = cne, p = p->fa;
}
}
}
char S[MAXN + 5], T[MAXN + 5];
int main() {
init(); scanf("%s", S);
int lenS = strlen(S);
for(int i=0;i<lenS;i++)
sam_extend(S[i] - 'a');
for(int i=lenS;i>=1;i--)
for(sam *p=bin[i];p;p=p->nxt)
p->ans = p->mx;
while( scanf("%s", T) == 1 ) {
for(int i=lenS;i>=1;i--)
for(sam *p=bin[i];p;p=p->nxt)
p->tmp = 0;
int lenT = strlen(T), res = 0;
sam *nw = root;
for(int i=0;i<lenT;i++) {
while( nw && !nw->ch[T[i] - 'a'] )
nw = nw->fa;
if( !nw ) res = 0, nw = root;
else res = min(res, nw->mx), nw = nw->ch[T[i] - 'a'], res++;
nw->tmp = max(nw->tmp, res);
}
for(int i=lenS;i>=1;i--)
for(sam *p=bin[i];p;p=p->nxt) {
if( p->tmp ) p->fa->tmp = p->fa->mx;
p->ans = min(p->ans, p->tmp);
}
}
int ans = 0;
for(int i=lenS;i>=1;i--)
for(sam *p=bin[i];p;p=p->nxt)
ans = max(ans, p->ans);
printf("%d
", ans);
}
@details@
一定要沿着 fa 更新。
再强调一遍，一定要沿着 fa 更新。