BZOJ 2946: [Poi2000]公共串

Description

給出幾個由小寫字母構成的單詞，求它們最長的公共子串的長度。
           

任務：

l 讀入單詞

l 計算最長公共子串的長度

l 輸出結果

Input

檔案的第一行是整數 n，1<=n<=5，表示單詞的數量。接下來n行每行一個單詞，隻由小寫字母組成，單詞的長度至少為1，最大為2000。

Output

僅一行，一個整數，最長公共子串的長度。

Sample Input

3

abcb

bca

acbc

Sample Output

２

分析

先對第一個字元串建構sam，然後對于其餘每個串，記錄每個位置在字尾自動機上比對到的最大長度，然後有一個特别關鍵的轉移就是每個兒子節點的mx傳給其parents，再在所有位置裡面找一個最大的即可。

代碼

#include <bits/stdc++.h>

const int N = ;

int ch[N][],max[N],fa[N];

int last,cnt;

void extand(int x)
{
    int p,q,np,nq;
    p = last, np = last = ++cnt;
    max[np] = max[p] + ;
    for (; !ch[p][x] && p; p = fa[p])
        ch[p][x] = np;
    if (!p)
        fa[np] = ;
    else
    {
        q = ch[p][x];
        if (max[q] == max[p] + )
            fa[np] = q;
        else
        {
            nq = ++cnt;
            max[nq] = max[p] + ;
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            fa[nq] = fa[q];
            fa[q] = fa[np] = nq;
            for (; ch[p][x] == q; p = fa[p])
                ch[p][x] = nq;
        }
    }
}

int n,m;
int b[N],c[N];
int mx[N];
int ans[N];

char s[N];

void preWork()
{
    for (int i = ; i <= cnt; i++)
        b[max[i]]++;
    for (int i = ; i <= n; i++)
        b[i] += b[i - ];
    for (int i = ; i <= cnt; i++)
        c[b[max[i]]--] = i;
    for (int i = ; i <= cnt; i++)
        ans[i] = max[i];
}

void solve()
{
    memset(mx, , sizeof(mx));
    int now = , len = ;
    for (int i = ; i <= n; i++)
    {
        s[i] -= 'a';
        for (; !ch[now][s[i]] && now; now = fa[now]);
        if (!now)
            now = , len = ;
        else len = std::min(len, max[now]) + , now = ch[now][s[i]];
        mx[now] = std::max(mx[now], len);
    }
    for (int i = cnt; i >= ; i--)
        mx[fa[c[i]]] = std::max(mx[fa[c[i]]], mx[c[i]]);
    for (int i = ; i <= cnt; i++)
        ans[i] = std::min(ans[i], mx[i]);
}

int main()
{
    scanf("%d",&m);
    scanf("%s",s + );
    n = strlen(s + );
    last = cnt = ;
    for (int i = ; i <= n; i++)
        extand(s[i] - 'a');
    preWork();
    for (int i = ; i < m; i++)
    {
        scanf("%s", s + );
        n = strlen(s + );
        solve();
    }
    int w = ;
    for (int i = ; i <= cnt; i++)
        w = std::max(w, ans[i]);
    printf("%d\n",w);
}