题解 P2463 【[SDOI2008]Sandy的卡片】
Creeper_LKF
2017-12-06 22:18:30
既然大家都用KMP或后缀数组，那本蒟蒻发一发后缀自动机的题解吧。
可以先了解一下后缀自动机，在本题中，它的应用是统计子串出现次数及长度。
后缀自动机可以匹配（接受）给定母串的所有子串。
于是在这道题中，我们把输入差分一下，发现样例转换成
1 1
1 1 4
然后答案是2？
然而第一个数无效（显然的）。答案应该是去掉第一个数之后的所有串的
最长公共###子串 +1
子串？符合胃口。于是我们要求最长公共子串在n个串中都出现过。
现在先假设你已经学完了后缀自动机
如何统计出现了n次？
我们以某一个位置作为开头，然后扫描这个字符所对应在后缀自动机的节点（注意不要重复），然后跟着pre数组向上走，每走一个节点给它的次数++，于是如果一个点被走了n次，那么说明它在n个串中都出现过了（可以根据pre数组的定义推导）。
如何获取长度？
其实就是step，也是定义，也就是原定义中跳转节点的长度。
代码如下（理论复杂度O(nm)\*O(n-)）：
```cpp
#include <cstring>
#include <cstdio>
#include <cctype>
#include <map>
using namespace std;
#define MAXN 1010
#define MAXM 2000020
#define INF 0x3f3f3f3f
inline char get_char(){
static char buf[500001], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 500000, stdin), p1 == p2) ? EOF : *p1 ++;
}
inline int read(){
int num = 0;
char c;
while (isspace(c = get_char()));
while (num = num * 10 + c - 48, isdigit(c = get_char()));
return num;
}
inline int upmax(int &a, const int &b){
if(a < b) a = b;
return a;
}
int n, m[MAXN], s[MAXN][MAXN], size[MAXM];
namespace SAM{
int cnt = 1, lst = 1;
map<int, int> son[MAXM];
int pre[MAXM], step[MAXM];
inline void Insert(int tar){
int p = lst, np = ++cnt;
for(lst = np, step[np] = step[p] + 1;p && !son[p][tar]; p = pre[p]) son[p][tar] = np;
if(!p) pre[np] = 1;
else {
int q = son[p][tar];
if(step[p] + 1 == step[q]) pre[np] = q;
else {
int nq = ++cnt;
step[nq] = step[p] + 1;
son[nq] = son[q];
for(pre[nq] = pre[q], pre[q] = pre[np] = nq; son[p][tar] == q; p = pre[p]) son[p][tar] = nq;
}
}
}
}
int vis[MAXM];
inline int Get_Ans(){
int ret = 1;
for(int i = 1; i <= n; i++){
int p = 1, *tp = s[i];
for(int j = 2; j <= m[i]; j++){
p = SAM::son[p][tp[j] - tp[j - 1]];
int tmp = p;
while(vis[tmp] != i){
vis[tmp] = i;
size[tmp]++;
tmp = SAM::pre[tmp];
}
}
}
for(int i = 1; i <= SAM::cnt; i++)
if(size[i] == n)
upmax(ret, SAM::step[i] + 1);
return ret;
}
int main(){
n = read();
for(int i = 1; i <= n; i++){
m[i] = read();
int *p = s[i];
for(int j = 1; j <= m[i]; j++){
p[j] = read();
if(j != 1) SAM::Insert(p[j] - p[j - 1]);
}
}
printf("%d", Get_Ans());
return 0;
}
```