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

把s数组清空了就A了……

Posted by function2 at 2015-11-16 09:25:35 on Problem 1226
#include<iostream>
#include<cstdio>
#include<cstring>
#define clr(a,b) memset(a,b,sizeof(a))
#define maxl 21000
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int sa[maxl+10],t1[maxl+10],t2[maxl+10],c[maxl+10],s[maxl+10],pos[maxl+10];
char buf[110];
void buildsa(int n,int m){
	s[n]=0;
	int i,p=1,*x=t1,*y=t2;
	for(i=0;i<m;i++)c[i]=0;
	for(i=0;i<n;i++)c[x[i]=s[i]]++;
	for(i=1;i<m;i++)c[i]+=c[i-1];
	for(i=n-1;~i;i--)sa[--c[x[i]]]=i;
	for(int k=1;p<n;k<<=1,m=p){
		for(p=0,i=n-k;i<n;i++)y[p++]=i;
		for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
		for(i=0;i<m;i++)c[i]=0;
		for(i=0;i<n;i++)c[x[y[i]]]++;
		for(i=1;i<m;i++)c[i]+=c[i-1];
		for(i=n-1;~i;i--)sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		x[sa[0]]=0;p=1;
		for(i=1;i<n;i++)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
	}
}
int ra[maxl+10],hei[maxl+10];
void buildhei(int n){
	int i,j,k=0;
	for(i=0;i<=n;i++)ra[sa[i]]=i;
	for(i=0;i<n;hei[ra[i++]]=k)
		for(k-=k>0,j=sa[ra[i]-1];s[i+k]==s[j+k];k++);
}
int vis[maxl+10];
bool judge(int x,int n,int len){
	int cur=1,cnt=0;
	clr(vis,-1);
	for(int i=0;i<=len;i++){
		if(hei[i]<x){
			cnt=0;
			cur=i+1;
		}else{
			if(vis[pos[sa[i]]]!=cur){
				vis[pos[sa[i]]]=cur;
				cnt++;
			}
			if(vis[pos[sa[i-1]]]!=cur){
				vis[pos[sa[i-1]]]=cur;
				cnt++;
			}
			if(cnt==n)return 1;
		}
	}
	return 0;
}
int main(){
	freopen("1226.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--){
		clr(pos,0);
		int tot=0,n,r=200;
		scanf("%d",&n);
		if(n==1){
			scanf("%s",buf);
			printf("%d\n",strlen(buf)); 
			continue;
		}
		clr(s,0);//就是这里……不明觉厉
		for(int i=1;i<=n;i++){
			scanf("%s",buf);
			int len=strlen(buf);
			r=min(r,len);
			for(int j=0;j<len;j++)pos[tot]=i,s[tot++]=buf[j];
			pos[tot]=i;
			s[tot++]=i*2+150;
			for(int j=len-1;~j;j--)pos[tot]=i,s[tot++]=buf[j];
			pos[tot]=i;
			s[tot++]=i*2+151;
		}
		buildsa(tot+1,360);
		buildhei(tot);
		if(!judge(1,n,tot))puts("0");
		else{
			int l=1,ans;
			while(l<=r){
				int m=(l+r)/2;
				if(judge(m,n,tot))l=m+1,ans=m;
				else r=m-1;
			}
			printf("%d\n",ans);
		}
	}
	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