求多串的最长公共字串.
法1: 二分长度+hash 传送门
法2: 二分+后缀数组 传送门
法3: 后缀自动机
拿第一个串建自动机,然后用其他串在上面匹配.每次求出SAM上每个节点的最长匹配长度后,再在全局取最小值(因为是所有串的公共串)就行了.
CODE
#include<bits/stdc++.h>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 2005;
const int C = 26;
int m, lk[MAXN<<1], ch[MAXN<<1][C], len[MAXN<<1], mx[MAXN<<1], mn[MAXN<<1], bin[MAXN<<1], seq[MAXN<<1], sz, last;
inline void init() {
last = sz = 0; ++sz;
lk[0] = -1; len[0] = 0;
}
inline void Copy(int A, int B) {
lk[A] = lk[B];
memcpy(ch[A], ch[B], sizeof ch[B]);
}
inline int insert(int p, int c) {
int cur = sz++; last = cur;
len[cur] = len[p] + 1;
for(; ~p && !ch[p][c]; p = lk[p]) ch[p][c] = cur;
if(p == -1) lk[cur] = 0;
else {
int q = ch[p][c];
if(len[p] + 1 == len[q]) lk[cur] = q;
else {
int x = sz++;
len[x] = len[p] + 1;
Copy(x, q);
lk[cur] = lk[q] = x;
for(; ~p && ch[p][c] == q; p = lk[p]) ch[p][c] = x;
}
}
return last;
}
inline void Match(char *s) {
int p = 0, now = 0, j = 0;
for(int c; s[j]; ++j) {
if(ch[p][c=s[j]-'a'])
++now, p = ch[p][c];
else {
for(; ~p && !ch[p][c]; p = lk[p]);
if(p == -1) now = p = 0;
else now = len[p] + 1, p = ch[p][c];
}
mx[p] = max(mx[p], now);
}
for(int i = sz-1; i; --i) {
mn[seq[i]] = min(mn[seq[i]], mx[seq[i]]);
mx[lk[seq[i]]] = max(mx[lk[seq[i]]], mx[seq[i]]);
mx[seq[i]] = 0;
}
}
char s[MAXN];
int main() {
read(m); scanf("%s", s);
if(--m == 0) return printf("%d
", strlen(s)), 0;
init(); int p = 0;
for(int i = 0; s[i]; ++i) p = insert(p, s[i]-'a');
for(int i = 0; i < sz; ++i) ++bin[mn[i] = len[i]];
for(int i = 1; i < sz; ++i) bin[i] += bin[i-1];
for(int i = sz-1; ~i; --i) seq[--bin[len[i]]] = i;
while(m--) scanf("%s", s), Match(s);
int ans = 0;
for(int i = 1; i < sz; ++i)
ans = max(ans, mn[i]);
printf("%d
", ans);
}