【SP1811】 LCS - Longest Common Substring（后缀自动机）

题目链接

对第一个串建出\(SAM\)，然后用第二个串去匹配。

如果能往下走就往下走，不能的话就跳parent tree的父亲，直到能走为止。如果跳到\(0\)了还是不能走，重新匹配。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 1000010;

struct SAM{

    int ch[26];

    int len, fa;

}sam[MAXN << 1];

int las = 1, cnt = 1;

inline void add(int c){

    int p = las; int np = las = ++cnt;

    sam[np].len = sam[p].len + 1;

    for(; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np;

    if(!p) sam[np].fa = 1;

    else{

        int q = sam[p].ch[c];

        if(sam[q].len == sam[p].len + 1) sam[np].fa = q;

        else{

            int nq = ++cnt; sam[nq] = sam[q];

            sam[nq].len = sam[p].len + 1;

            sam[q].fa = sam[np].fa = nq;

            for(; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq;

        }

    }

}

char a[MAXN], b[MAXN];

int ans;

int main(){

    scanf("%s", a + 1);

    scanf("%s", b + 1);

    int lena = strlen(a + 1), lenb = strlen(b + 1);

    for(int i = 1; i <= lena; ++i)

        add(a[i] - 'a');

    int p = 1, len = 0;

    for(int i = 1; i <= lenb; ++i){

        if(sam[p].ch[b[i] - 'a'])

            ++len, p = sam[p].ch[b[i] - 'a'];

        else{

            while(!sam[p].ch[b[i] - 'a'] && p) p = sam[p].fa;

            if(!p) p = 1, len = 0;

            else len = sam[p].len + 1, p = sam[p].ch[b[i] - 'a'];

        }

        ans = max(ans, len);

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

【SP1811】 LCS - Longest Common Substring（后缀自动机）

最新文章

热门文章