SPOJ 1812 LCS2 后缀自动机

求给定n个串的最长公共子串。

先对一个构造SAM。

接着每个串匹配一次，并处理出各状态能匹配到的最大长度（要注意沿Parent树更新），于是总的就是各状态的最小值。

#include <cstring>
#include <cstdio>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;
#define FOR(i,j,k) for(i=j;i<=k;++i)
const int rt = , N = ;
int last = , cnt = , len = ;
int ch[N][], fa[N], ma[N], rl[N], rr[N], b[N], bucket[N >> ];
char str[N >> ];
void add(char c) {
    int np = ++cnt, p = last, q, nq; last = np; rl[np] = rr[np] = ma[np] = ++len;
    while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
    if (!p) fa[np] = rt;
    else {
        q = ch[p][c];
        if (ma[q] == ma[p] + ) fa[np] = q;
        else {
            nq = ++cnt; memcpy(ch[nq], ch[q], sizeof ch[q]);
            rl[nq] = ma[nq] = ma[p] + ;
            fa[nq] = fa[q]; fa[q] = fa[np] = nq;
            while (p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
        }
    }
}

int main() {
    int i, n, p, y, c, ans = ;
    scanf("%s", str + ); n = strlen(str + );
    for(i=;str[i];++i) add(str[i] - 'a');
    FOR(i,,cnt) ++bucket[ma[i]];
    FOR(i,,n) bucket[i] += bucket[i - ];
    for(i=cnt;i;--i) b[bucket[ma[i]]--] = i;
    while (scanf("%s", str + ) != EOF) {
        p = rt; y = ;
        for(i=;str[i];++i) {
            c = str[i] - 'a';
            if (ch[p][c]) {
                p = ch[p][c];
                rr[p] = max(rr[p], ++y);
            } else {
                while (p && !ch[p][c]) p = fa[p];
                if (p) rr[p] = max(rr[p], y = ma[p] + ), p = ch[p][c];
                else p = rt, y = ;
            }
        }
        for(i=cnt;i;--i) {
            rl[b[i]] = min(rl[b[i]], rr[b[i]]);
            rr[fa[b[i]]] = max(rr[fa[b[i]]], rr[b[i]]);
            rr[b[i]] = ;
        }
    }
    FOR(i,,cnt) ans = max(ans, rl[i]);
    printf("%d", ans);
    return ;
}
           

LCS2 - Longest Common Substring II

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is a bit harder, for some given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn’t exist, print “0” instead.

Example

Input:

alsdfkjfjkdsal

fdjskalajfkdsla

aaaajfaaaa

Output:

2