SP1811 LCS - Longest Common Substring

求两个字符串最长公共子串的长度。

对于第一个串S，建立SAM，之后对于第二个串T，我们在上面和S进行匹配。首先从\(t_0\)开始，如果能成功匹配的话，那么我们让长度+1，同时更新答案。如果失配，那我们就跳parent树转移到其父节点的位置，并且把当前匹配长度变为其最长后缀长度即可。最后统计一下输出匹配的最大长度。

#include<bits/stdc++.h>
#define rep(i,a,n) for(register int i = a;i <= n;i++)
#define per(i,n,a) for(register int i = n;i >= a;i--)
#define enter putchar('\n')
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define sc second
using namespace std;
typedef long long ll;
const int M = 500005;
const int N = 10000005;

int read()
{
    int ans = 0,op = 1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
    while(ch >='0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
    return ans * op;
}

char s[M],t[M];
int n,m,ans,pos;

struct SuffixAutomaton
{
    int last,cnt,ch[M<<1][26],fa[M<<1],l[M<<1];
    void extend(int c)
    {
        int p = last,np = ++cnt;
        last = cnt,l[np] = l[p] + 1;
        while(p && !ch[p][c]) ch[p][c] = np,p = fa[p];
        if(!p) {fa[np] = 1;return;}
        int q = ch[p][c];
        if(l[q] == l[p] + 1) fa[np] = q;
        else
        {
            int nq = ++cnt;
            l[nq] = l[p] + 1,memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq] = fa[q],fa[np] = fa[q] = nq;
            while(ch[p][c] == q) ch[p][c] = nq,p = fa[p];
        }
    }
    void match(char *a)
    {
        int v = 1,len = 0;
        //rep(i,0,m-1) printf("%c ",a[i]);enter;
        rep(i,0,m-1)
        {
            //printf("#%d %d %d\n",v,len,pos);
            int c = a[i] - 'a';
            while(!ch[v][c] && v != 1) v = fa[v],len = l[v];
            if(ch[v][c]) 
            {
                v = ch[v][c],len++;
                if(len > ans) ans = len;
            }
        }
    }
}SAM;

int main()
{
    scanf("%s",s+1),n = strlen(s+1);
    scanf("%s",t+1),m = strlen(t+1);
    SAM.cnt = SAM.last = 1;
    rep(i,1,n) SAM.extend(s[i] - 'a');
    SAM.match(t+1);
    printf("%d\n",ans);
    return 0;
}

SP1811 LCS - Longest Common Substring

推荐阅读