Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
后缀自动机做法#define MAXN 200010UL #define MAXC 26UL #define MAXL 2010UL #include <bitset> #include <stdio.h> #include <string.h> #include <algorithm> typedef std::bitset<101> bit_; int n,cnt,tail,len[MAXN],son[MAXN][MAXC],pre[MAXN],Ans[MAXN],max_length,sta[MAXN]; char s[MAXL]; bit_ flag[MAXN]; inline bool comp(int a,int b){ if(len[a]!=len[b]) return len[a]<len[b]; return a<b; } struct Suffix_AutoMaton{ inline int Push(int p){ len[++cnt]=p; return cnt; } inline void Rel(){tail=0;return;} inline void Clear(){ cnt=tail=max_length=0; memset(len,0,sizeof(len)); memset(son,0,sizeof(son)); memset(pre,0,sizeof(pre)); memset(flag,0,sizeof(flag)); return; } inline void Extend(int ch,int id){ int p=tail,np,q,nq; np=son[p][ch]; if(np){ if(len[np]==len[p]+1) tail=np; else{ q=np; nq=Push(len[p]+1); memcpy(son[nq],son[q],sizeof(son[nq])); pre[nq]=pre[q];pre[q]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; tail=nq; } } else{ np=Push(len[tail]+1); for(;!son[p][ch];p=pre[p]) son[p][ch]=np; if(!p&&son[0][ch]==np) pre[np]=0; else{ q=son[p][ch]; if(len[q]==len[p]+1) pre[np]=q; else{ nq=Push(len[p]+1); memcpy(son[nq],son[q],sizeof(son[nq])); pre[nq]=pre[q]; pre[q]=pre[np]=nq; for(;son[p][ch]==q;p=pre[p]) son[p][ch]=nq; } } tail=np; } flag[tail][id]=1; return; } inline void Build(){ for(int i=1;i<=n;i++){ Rel();scanf("%s",s); for(int j=0,R=strlen(s);j<R;j++) Extend(s[j]-'a',i); } static int h[MAXN]; for(int i=0;i<=cnt;i++) h[i]=i; std::sort(h,h+cnt+1,comp); for(int i=cnt;i>=0;i--) flag[pre[h[i]]]|=flag[h[i]]; for(int i=0;i<=cnt;i++) Ans[i]=flag[i].count(); return; } inline void GetAns(int p,int cur_length){ if(Ans[p]<=n) return; if(cur_length>max_length) max_length=cur_length; for(int i=0;i<MAXC;i++) if(son[p][i]) GetAns(son[p][i],cur_length+1); return; } inline void dfs(int p,int cur_length){ if(Ans[p]<=n) return; if(cur_length==max_length){for(int i=1;i<=sta[0];i++) putchar('a'+sta[i]);puts("");} for(int i=0;i<MAXC;i++) if(son[p][i]){ sta[++sta[0]]=i; dfs(son[p][i],cur_length+1); --sta[0]; } return; } inline void Solve(){ n>>=1; GetAns(0,0); if(!max_length) puts("?"); else dfs(0,0); putchar('\n');//case end . return; } }SAM; int main(){ while(scanf("%d",&n)&&n){ SAM.Clear(); SAM.Build(); SAM.Solve(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator