Submission #232371
Source Code Expand
#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 Info
Submission Time
2014-09-15 13:43:20+0900
Task
F - Longest Match
User
fura2
Language
C++ (GCC 4.4.7)
Score
100
Code Size
4322 Byte
Status
AC
Exec Time
208 ms
Memory
29180 KB
Compile Error
./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
Judge Result
Set Name
All
Score / Max Score
100 / 100
Status
Set Name
Test Cases
All
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
Case Name
Status
Exec Time
Memory
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