首页 > 代码库 > BZOJ 2946: [Poi2000]公共串

BZOJ 2946: [Poi2000]公共串

Description

最长公共子串,\(n\leqslant 5,l\leqslant 1000\)

Solution

SAM...

对于同一字符串取max,不用字符串取min

Code

/**************************************************************    Problem: 2946    User: BeiYu    Language: C++    Result: Accepted    Time:1012 ms    Memory:2308 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; const int N = 4050;const int M = 30;const int oo = 0x3f3f3f3f; struct SAM {    int rt,lst,cnt;    int go[N][M],par[N],val[N],vis[N],cv[N],mi[N][M];         void init() { rt=lst=cnt=1; }    void Add(int x) {        int p=lst,np=++cnt;val[np]=val[p]+1;        while(p && !go[p][x]) go[p][x]=np,p=par[p];        if(!p) par[np]=rt;        else {            int q=go[p][x];            if(val[q]==val[p]+1) par[np]=q;            else {                int nq=++cnt;                val[nq]=val[p]+1,par[nq]=par[q],par[np]=par[q]=nq;                memcpy(go[nq],go[q],sizeof(go[q]));                while(p && go[p][x]==q) go[p][x]=nq,p=par[p];            }        }lst=np;    }    void insert(int id,char *s) {        int l=strlen(s),x=rt,lt=0;        for(int i=0;i<l;i++) {            int v=s[i]-‘a‘+1;            while(x!=rt && !go[x][v]) x=par[x],lt=val[x];            if(go[x][v]) x=go[x][v],lt++;            for(int t=x;t;t=par[t]) mi[t][id]=max(mi[t][id],min(lt,val[t]));        }    }    int get_ans(int x,int n) {        int res=oo;        for(int i=1;i<n;i++) res=min(res,mi[x][i]);        for(int i=1;i<M;i++) if(go[x][i]) res=max(res,get_ans(go[x][i],n));        return res;    }}py; int n;char s[N]; int main() {    scanf("%d",&n);    scanf("%s",s);    int l=strlen(s);    if(n==1) return printf("%d\n",l),0;    py.init();    for(int i=0;i<l;i++) py.Add(s[i]-‘a‘+1);    for(int i=1;i<n;i++) scanf("%s",s),py.insert(i,s);    printf("%d\n",py.get_ans(py.rt,n));    return 0;}

  

BZOJ 2946: [Poi2000]公共串