首页 > 代码库 > BZOJ 4698: Sdoi2008 Sandy的卡片

BZOJ 4698: Sdoi2008 Sandy的卡片

Description

最长公共子串..

Solution

后缀自动机..

差分以后同上题...

Code

/**************************************************************    Problem: 4698    User: BeiYu    Language: C++    Result: Accepted    Time:100 ms    Memory:2468 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; const int N = 250;const int M = 150;const int K = 1050;const int oo = 0x3f3f3f3f; struct SAM {    int rt,lst,cnt;    int go[N][M],par[N],val[N],vis[N],cv[N],mi[N][K];         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,int l,int *s) {        int x=rt,lt=0;        for(int i=1;i<=l;i++) {            int v=s[i];            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,l;int s[N],t[N]; void read() {    scanf("%d",&l);l--;    for(int i=0;i<=l;i++) scanf("%d",&s[i]);    for(int i=1;i<=l;i++) t[i]=s[i]-s[i-1];}int main() {    scanf("%d",&n);    read();    py.init();    for(int i=1;i<=l;i++) py.Add(t[i]);    for(int i=1;i<n;i++) read(),py.insert(i,l,t);    printf("%d\n",py.get_ans(py.rt,n)+1);    return 0;}

  

BZOJ 4698: Sdoi2008 Sandy的卡片