| ||||||||||
| 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