题解 P2463 【[SDOI2008]Sandy的卡片】

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-)):

#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;
}