Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

后缀自动机做法

Posted by stdafx_dev at 2016-01-17 12:36:59 on Problem 3294
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator