DZY 's BLOG

求两个串的最长公共子串。串长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;
}

拿SAM来求字符串的最小表示很煞笔吧、好吧、只是拿来练习SAM用的、

把字符串自复制一遍、然后建SAM、然后从root开始跑，每次都跑最小编号的结点，在上面跑|S|个结点。然后输出当前结点的信息就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct SAMNode{
    int ch[26],fa,len;
    inline void init(){
        fa=-1; len=0; memset(ch,0xff,sizeof(ch));
    }
}T[50010];
char s[10010];
int tot,last; 
void add(int c){
    int end=++tot; T[end].init();
    int tmp=last;
    T[end].len=T[last].len+1;
    while(tmp!=-1 && T[tmp].ch[c]==-1){
        T[tmp].ch[c]=end;
        tmp=T[tmp].fa;
    }if(!~tmp) T[end].fa=0;
    else{
        int next=T[tmp].ch[c];
        if(T[tmp].len+1==T[next].len) T[end].fa=next;
        else{
            int np=++tot; T[np].init();
            T[np]=T[next];
            T[np].len=T[tmp].len+1;
            T[end].fa=T[next].fa=np;
            while(tmp!=-1 && T[tmp].ch[c]==next){
                T[tmp].ch[c]=np;
                tmp=T[tmp].fa;
            }
        }
    }last=end;
}int main(){
    int tc;
    scanf("%d",&tc);
    while(tc--){
        tot=0; last=0; T[0].init();
        scanf("%s",s);
        int n=strlen(s);
        for(int i=0;i<n;i++) add(s[i]-'a');
        for(int i=0;i<n;i++) add(s[i]-'a');
        int o=0;
        for(int i=0;i<n;i++) for(int j=0;j<26;j++) if(~T[o].ch[j]){
            o=T[o].ch[j]; break;
        }printf("%d\n",T[o].len-n+1);
    }return 0;
}