求两个串的最长公共子串。串长250000。

很像上一道题处理d[i]数组。

给第一个串建后缀自动机。

第二个串在上面跑即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510010;
char buf[maxn],*pt=buf;
int l[maxn],fa[maxn],c[maxn][26],rt=1,tot=1,tail=1;
void add(int x){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!c[p][x];p=fa[p])   c[p][x]=np;
    if(!p){ fa[np]=rt;   return;}
    if(l[p]+1==l[q=c[p][x]]){   fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(c[r],c[q],sizeof(c[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&c[p][x]==q;p=fa[p]) c[p][x]=r;
}int main(){
    fread(buf,1,510000,stdin);  char ch;
    while((ch=*pt++)!='\n') add(ch-'a');
    int p=rt,k=0,x,An=0;    
    while((ch=*pt++)!='\n'){
        if(c[p][x=ch-'a'])    ++k,p=c[p][x],An=max(k,An); else{
            for(;p&&!c[p][x];p=fa[p]);
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=c[p][x],An=max(k,An);
        }
    }printf("%d\n",An); return 0;
}

• 相关文章