Chlience

【题解】SPOJ LCS2 Longest Common Substring II
Probelm传送门 >ω<题目大意:给定 $n$ 个字符串 ,求其最长公共子串的长度$1\leq n \leq ...
扫描右侧二维码阅读全文
13
2018/10

【题解】SPOJ LCS2 Longest Common Substring II

Probelm

传送门 >ω<

题目大意:
给定 $n$ 个字符串 ,求其最长公共子串的长度

$1\leq n \leq 10$
$1 \leq lenth(s) \leq 100000$

Solution

看起来很难,实际上非常暴力的题

设最长公共子串长度为 $len$ ,那么显然最后一个串的某个长度为 $len$ 的子串能与前 $n - 1$ 个串匹配
而 SAM 在匹配时能够求出每个位置作为结束位置时匹配的最大长度

所以将前 $n - 1$ 个串分别建出 SAM ,用第 $n$ 个串直接匹配,同时记录每个位置作为结尾位置与模板串匹配的最大长度

找出匹配长度最大的位置作为答案即可

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct SAM {
    int ch[N << 1][26] , fa[N << 1];
    int siz[N << 1] , l[N << 1];
    int cnt , last , len;
    int ans[N];
    void ins(int c) {
        int x = last , nx = ++ cnt; last = nx;
        l[nx] = l[x] + 1; siz[nx] = 1;
        for(; x && !ch[x][c] ; x = fa[x]) ch[x][c] = nx;
        if(!x) fa[nx] = 1;
        else {
            int y = ch[x][c];
            if(l[y] == l[x] + 1) fa[nx] = y;
            else {
                int ny = ++cnt; l[ny] = l[x] + 1;
                memcpy(ch[ny] , ch[y] , sizeof(ch[y]));
                fa[ny] = fa[y]; fa[y] = fa[nx] = ny;
                for(; ch[x][c] == y ; x = fa[x]) ch[x][c] = ny;
            }
        }
    }
    void insert(char *s) {
        len = strlen(s);
        last = cnt = 1;
        for(int i = 0 ; i < len ; ++ i) ins(s[i] - 'a');
    }
    void work(char *s) {
        len = strlen(s);
        int x = 1 , lenth = 0;
        for(int i = 0 ; i < len ; ++ i) {
            int c = s[i] - 'a';
            if(ch[x][c]) {x = ch[x][c]; ++ lenth;}
            else {
                while(x && !ch[x][c]) x = fa[x];
                if(x) {lenth = l[x] + 1; x = ch[x][c];}
                else {lenth = 0; x = 1;}
            }
            ans[i] = lenth;
        }
    }
}sam[11];
int get(int pos , int cnt) {
    int ans = N;
    for(int i = 1 ; i < cnt ; ++ i) ans = min(ans , sam[i].ans[pos]);
    return ans;
}
char s[N] , str[N];
int cnt = 0;
int main() {
    while(~scanf("%s" , s)) {
        if(cnt) sam[cnt].insert(str); ++ cnt;
        swap(s , str);
    }
    for(int i = 1 ; i < cnt ; ++ i)
        sam[i].work(str);
    int n = strlen(str);
    int longest = 0;
    for(int i = 0 ; i < n ; ++ i)
        longest = max(longest , get(i , cnt));
    printf("%d\n" , longest);
}
Last modification:October 13th, 2018 at 10:50 pm

Leave a Comment