首页 > 代码库 > 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]公共串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。