Chlience

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

【题解】SPOJ LCS Longest Common Substring

Probelm

传送门 >ω<

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

$1 \leq lenth(a) , lenth(b) \leq 250000$

Solution

既然要求最长公共子串,能够保留所有子串信息的数据结构我们使用 SAM

考虑将串 $s$ 建出 SAM ,然后用串 $t$ 在 SAM 上进行匹配

如何匹配?

  • 首先,设当前状态为 $x$ ,匹配到了第 $i$ 个字符 $c$ ,匹配长度为 $len$
  • 若 $ch[x][c] \neq 0$ ,即有向 $c$ 的转移,则 $x = ch[x][c] , len = len + 1 , i = i + 1$
  • 若 $ch[x][c] = 0$ ,即没有向 $c$ 的转移

    • 通过 $fa$ 去找到能够转到 $c$ 的最长后缀,即 $x = fa[x]$,重复过程直到 $ch[x][c] \neq 0$ 或者 $x = 0$
    • 若 $ch[x][c] \neq 0$ 那么状态进行转移,匹配长度 $lenth = l[x] + 1$ ,状态 $x = ch[x][c]$
    • 若 $x = 0$ 则没有任何子串含有 $c$ 。所以将长度 $lenth = 0$ ,状态 $x = 1$ (也就是根)

同时,在匹配时维护一个匹配长度最大值即可

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
struct SAM {
    int ch[N << 1][26] , fa[N << 1];
    int siz[N << 1] , l[N << 1];
    int cnt , last , len;
    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 , ans = 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 = max(ans , lenth);
        }
        printf("%d\n" , ans);
    }
}sam;
char s[N] , t[N];
int main() {
    scanf("%s %s" , s , t);
    sam.insert(s); sam.work(t);
    return 0;
}

Ps:不要问我为什么写 SAM 的时候之前用 $slink$ 和 $trans$ 然后这里又用 $fa$ 和 $ch$
因为真是太*******难写了..

Last modification:October 13th, 2018 at 10:50 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment