题目地址：SPOJ：SPOJ.com – Problem LCS2、洛谷：【SP1812】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.

题意简述

给定一些字符串，求出它们的最长公共子串。

输入输出格式

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

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

输入输出样例

输入样例#1：

alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa

输出样例#1：

2

题解

考虑一个SAM求两个串LCS的做法，是把一个串建SAM另一个串在上面跳。在这一题，我们仍然可以用一个串建LCS，其他串在SAM上跳的方法，在跳的过程中，在每个经过的节点上记下以该节点结尾的LCS长度的最大值，由于后缀链接可以传递LCS，需要用该节点的最大值沿后缀链接更新前缀树中父亲节点的最大值。最后统计出每个节点在所有串中LCS情况的最小值的最大值即可。
复杂度O(n)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for (; !isdigit(c); c = fgc()) if (c == '-') neg = -1;
    for (; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

struct SuffixAutomaton {
    int last, tot, ch[MAXN << 1][26], nxt[MAXN << 1], len[MAXN << 1];
    SuffixAutomaton() {
        last = tot = 1;
    }
    inline void extend(int c) {
        int u = ++tot, v = last; 
        len[u] = len[v] + 1;
        for(; v && !ch[v][c]; v = nxt[v]) ch[v][c] = u;
        if(!v) {
            nxt[u] = 1;
        } else if(len[ch[v][c]] == len[v] + 1) {
            nxt[u] = ch[v][c];
        } else {
            int n = ++tot, o = ch[v][c]; len[n] = len[v] + 1;
            memcpy(ch[n], ch[o], sizeof(ch[o]));
            nxt[n] = nxt[o]; nxt[o] = nxt[u] = n;
            for(; v && ch[v][c] == o; v = nxt[v]) ch[v][c] = n;
        }
        last = u;
    } 
} sam;

char str[MAXN];
int a[MAXN << 1], c[MAXN << 1], mx[MAXN << 1], ans[MAXN << 1];

int main() {
    memset(ans, 0x3f, sizeof(ans));
    scanf("%s", str + 1);
    for(int i = 1; str[i]; i++) {
        sam.extend(str[i] - 'a');
    }
    for(int i = 1; i <= sam.tot; i++) c[sam.len[i]]++;
    for(int i = 1; i <= sam.tot; i++) c[i] += c[i - 1];
    for(int i = 1; i <= sam.tot; i++) a[c[sam.len[i]]--] = i;
    while(scanf("%s", str + 1) != EOF) {
        int len = 0, p = 1, c; 
        for(int i = 1; str[i]; i++) {
            c = str[i] - 'a';
            while(p && !sam.ch[p][c]) {
                p = sam.nxt[p]; len = sam.len[p];
            }
            if(p) {
                len++; p = sam.ch[p][c]; mx[p] = std::max(mx[p], len);
            } else {
                p = 1; len = 0;
            }
        }
        for(int i = sam.tot; i; i--) {
            int p = a[i];
            mx[sam.nxt[p]] = std::max(mx[sam.nxt[p]], std::min(mx[p], sam.len[sam.nxt[p]]));
            ans[p] = std::min(ans[p], mx[p]); mx[p] = 0;
        }
    }
    int res = 0;
    for(int i = 1; i <= sam.tot; i++) {
        res = std::max(res, ans[i]);
    }
    printf("%d", res);
    return 0;
}