Japan Alumni Group Summer Camp 2014 Day 4

Submission #232371

Source codeソースコード

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

#define tget(i) ((t[(i)/8]&mask[(i)%8]) ? 1 : 0)
#define tset(i,b) t[(i)/8]=((b) ? (mask[(i)%8]|t[(i)/8]) : ((~mask[(i)%8])&t[(i)/8]))
#define chr(i) (cs==sizeof(int) ? ((int *)s)[i] : ((char *)s)[i])
#define isLMS(i) (i>0 && tget(i) && !tget(i-1))

const char mask[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};

void get_buckets(const char *s,int *B,int n,int K,int cs,bool end){
	rep(i,K+1) B[i]=0;
	rep(i,n+1) B[chr(i)]++;
	int sum=0;
	rep(i,K+1){ sum+=B[i]; B[i]=(end?sum:sum-B[i]); }
}

void induceSAl(char *t,int *SA,const char *s,int *B,int n,int K,int cs,bool end){
	get_buckets(s,B,n,K,cs,end);
	rep(i,n+1){
		int j=SA[i]-1;
		if(j>=0 && !tget(j)) SA[B[chr(j)]++]=j;
	}
}

void induceSAs(char *t,int *SA,const char *s,int *B,int n,int K,int cs,bool end){
	get_buckets(s,B,n,K,cs,end);
	for(int i=n;i>=0;i--){
		int j=SA[i]-1;
		if(j>=0 && tget(j)) SA[--B[chr(j)]]=j;
	}
}

void SA_IS(int n,const char *s,int *SA,int K=128,int cs=1){
	char *t=(char *)malloc(n/8+1);
	tset(n-1,0);
	tset(n,1);
	for(int i=n-2;i>=0;i--){
		tset(i,(chr(i)<chr(i+1) || (chr(i)==chr(i+1) && tget(i+1)==1))?1:0);
	}

	int *B=(int *)malloc(sizeof(int)*(K+1));
	get_buckets(s,B,n,K,cs,true);
	rep(i,n+1) SA[i]=-1;
	for(int i=1;i<=n;i++) if(isLMS(i)) SA[--B[chr(i)]]=i;
	induceSAl(t,SA,s,B,n,K,cs,false);
	induceSAs(t,SA,s,B,n,K,cs,true);
	free(B);

	int n1=0;
	rep(i,n+1) if(isLMS(SA[i])) SA[n1++]=SA[i];
	for(int i=n1;i<=n;i++) SA[i]=-1;
	int name=0,prev=-1;
	rep(i,n1){
		int pos=SA[i];
		bool diff=false;
		rep(d,n+1){
			if(prev==-1 || chr(pos+d)!=chr(prev+d) || tget(pos+d)!=tget(prev+d)){
				diff=true;
				break;
			}
			else if(d>0 && (isLMS(pos+d) || isLMS(prev+d))) break;
		}
		if(diff){ name++; prev=pos; }
		pos=(pos%2==0)?pos/2:(pos-1)/2;
		SA[n1+pos]=name-1;
	}
	for(int i=n,j=n;i>=n1;i--) if(SA[i]>=0) SA[j--]=SA[i];

	int *SA1=SA,*s1=SA+n-n1+1;
	if(name<n1) SA_IS(n1-1,(char *)s1,SA1,name-1,sizeof(int));
	else        rep(i,n1) SA1[s1[i]]=i;

	B=(int *)malloc(sizeof(int)*(K+1));
	get_buckets(s,B,n,K,cs,true);
	for(int i=1,j=0;i<=n;i++) if(isLMS(i)) s1[j++]=i;
	rep(i,n1) SA1[i]=s1[SA1[i]];
	for(int i=n1;i<=n;i++) SA[i]=-1;
	for(int i=n1-1;i>=0;i--){
		int j=SA[i];
		SA[i]=-1;
		SA[--B[chr(j)]]=j;
	}
	induceSAl(t,SA,s,B,n,K,cs,false);
	induceSAs(t,SA,s,B,n,K,cs,true);
	free(B);

	free(t);
}

const int N_MAX=200001,LG_N_MAX=18;

template<class T>
class sparse_table_RMQ{
	T st[LG_N_MAX][N_MAX];

public:
	void build(int n,const T *a){
		rep(i,n) st[0][i]=a[i];
		for(int k=1;(1<<k)<n;k++) rep(i,n-(1<<k)+1) {
			st[k][i]=max(st[k-1][i],st[k-1][i+(1<<(k-1))]);
		}
	}

	T query(int l,int r)const{
		int k; for(k=0;(1<<(k+1))<r-l;k++);
		return max(st[k][l],st[k][r-(1<<k)]);
	}
};

// find the last appeared tar in s
pair<int,int> solve(int n,const char *s,const int *sa,const char *tar,const sparse_table_RMQ<int> &RMQ){
	int m=strlen(tar);
	int lo=0,hi=n+1;
	while(lo<hi){
		int mi=(lo+hi)/2;
		if(strncmp(s+sa[mi],tar,m)<0) lo=mi+1;
		else                          hi=mi; 
	}
	int left=lo;

	if(strncmp(s+sa[left],tar,m)!=0) return make_pair(-1,-1); // not found tar in s

	lo=0; hi=n;
	while(lo<hi){
		int mi=(lo+hi+1)/2;
		if(strncmp(s+sa[mi],tar,m)<=0) lo=mi;
		else                           hi=mi-1; 
	}
	int right=lo;

	int x=RMQ.query(left,right+1);
	return make_pair(x,x+m-1);
}

int main(){
	static char s[200001]; scanf("%s",s);
	int n=strlen(s);
	static int sa[200001];
	SA_IS(n,s,sa);

	static char s2[200001];
	static int sa2[200001];
	strcpy(s2,s);
	reverse(s2,s2+n);
	SA_IS(n,s2,sa2);

	static sparse_table_RMQ<int> RMQ1,RMQ2;
	RMQ1.build(n+1,sa);
	RMQ2.build(n+1,sa2);

	int q; scanf("%d",&q);
	while(q--){
		static char x[200001],y[200001]; scanf("%s%s",x,y);
		int m=strlen(x);
		reverse(x,x+m);
		pair<int,int> l=solve(n,s2,sa2,x,RMQ2);
		pair<int,int> r=solve(n,s ,sa ,y,RMQ1);
		if(l.first==-1 || r.first==-1){
			puts("0");
			continue;
		}
		l=make_pair((n-1)-l.second,(n-1)-l.first);
		printf("%d\n",l.first<=r.first&&l.second<=r.second?r.second-l.first+1:0);
	}

	return 0;
}

Submission

Task問題 F - Longest Match
User nameユーザ名 fura
Created time投稿日時
Language言語 C++ (GCC 4.4.7)
Status状態 AC
Score得点 100
Source lengthソースコード長 4322 Byte
File nameファイル名
Exec time実行時間 208 ms
Memory usageメモリ使用量 29180 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:143: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:158: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:160: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 00-sample1,00-sample2,00-sample3,01-invalid-bsearch1,01-xy-length-larger-than-S,10-small00,10-small01,10-small02,10-small03,10-small04,10-small05,10-small06,10-small07,10-small08,10-small09,10-small10,10-small11,10-small12,10-small13,10-small14,20-repetition-a,20-repetition-z,21-aab,22-query_str_lergest0,22-query_str_lergest1,30-large00,30-large01,30-large02,30-large03,30-large04,30-large05,30-large06,30-large07,30-large08,30-large09,30-large10,30-large11,30-large12,30-large13,30-large14

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00-sample1 AC 25 ms 924 KB
00-sample2 AC 26 ms 800 KB
00-sample3 AC 27 ms 924 KB
01-invalid-bsearch1 AC 25 ms 804 KB
01-xy-length-larger-than-S AC 26 ms 800 KB
10-small00 AC 27 ms 792 KB
10-small01 AC 27 ms 924 KB
10-small02 AC 25 ms 792 KB
10-small03 AC 27 ms 924 KB
10-small04 AC 27 ms 920 KB
10-small05 AC 27 ms 800 KB
10-small06 AC 27 ms 800 KB
10-small07 AC 27 ms 808 KB
10-small08 AC 25 ms 924 KB
10-small09 AC 27 ms 796 KB
10-small10 AC 28 ms 792 KB
10-small11 AC 26 ms 928 KB
10-small12 AC 25 ms 796 KB
10-small13 AC 27 ms 796 KB
10-small14 AC 26 ms 800 KB
20-repetition-a AC 208 ms 28836 KB
20-repetition-z AC 207 ms 28828 KB
21-aab AC 154 ms 28832 KB
22-query_str_lergest0 AC 147 ms 29172 KB
22-query_str_lergest1 AC 146 ms 29180 KB
30-large00 AC 147 ms 29048 KB
30-large01 AC 146 ms 29052 KB
30-large02 AC 146 ms 29048 KB
30-large03 AC 148 ms 28980 KB
30-large04 AC 146 ms 29040 KB
30-large05 AC 146 ms 29052 KB
30-large06 AC 147 ms 29048 KB
30-large07 AC 146 ms 29060 KB
30-large08 AC 146 ms 29048 KB
30-large09 AC 146 ms 29052 KB
30-large10 AC 152 ms 29056 KB
30-large11 AC 150 ms 29056 KB
30-large12 AC 150 ms 29056 KB
30-large13 AC 150 ms 29040 KB
30-large14 AC 151 ms 29040 KB