[SPOJ-LCS2]Longest Common Substring II 题解

[SPOJ-LCS2]Longest Common Substring II 题解

题目地址: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;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据