首页 > 代码库 > BZOJ3230: 相似子串

BZOJ3230: 相似子串

3230: 相似子串

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 913  Solved: 223
[Submit][Status]
Description

 

Input

输入第1行,包含3个整数N,Q。Q代表询问组数。
第2行是字符串S。
接下来Q行,每行两个整数i和j。(1≤i≤j)。

Output

输出共Q行,每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串,则输出-1。

Sample Input

5 3

ababa

3 5

5 9

8 10

 

Sample Output

18

16

-1

 

HINT

样例解释

第1组询问:两个子串是“aba”,“ababa”。f = 32 + 32 = 18。

第2组询问:两个子串是“ababa”,“baba”。f = 02 + 42 = 16。

第3组询问:不存在第10个子串。输出-1。


数据范围

N≤100000,Q≤100000,字符串只由小写字母‘a‘~‘z‘组成

Source

后缀数组+二分+RMQ

题解:

字典序第i?我们给每个排名为i后缀i一个ed[i]表示截止到排名i,一共有多少个本质不同的子串,然后在ed数组上lower_bound就可以找到子串的左端点,然后就知道右端点了。

然后求LCP?和LCS?(longest common suffix?)

两个后缀数组可以O(nlogn)预处理,O(1)查询。

hash可以O(n)预处理,O(logn)查询。

作为蒟蒻我写了后一种。。。

代码:

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 150000+5 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define ull unsigned long long  18 #define pa pair<int,int> 19 #define for0(i,n) for(int i=0;i<=(n);i++) 20 #define for1(i,n) for(int i=1;i<=(n);i++) 21 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 22 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 23 #define mod 1000000007 24 #define base 13131 25 using namespace std; 26 inline ll read() 27 { 28     ll x=0,f=1;char ch=getchar(); 29     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();} 30     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();} 31     return x*f; 32 } 33 int n,q,s[maxn],t[maxn],t2[maxn],c[maxn],sa[maxn],rk[maxn],h[maxn]; 34 ll ed[maxn]; 35 ull hash[maxn],mi[maxn]; 36 void getsa(int m) 37 { 38     int *x=t,*y=t2; 39     for0(i,m)c[i]=0; 40     for0(i,n)c[x[i]=s[i]]++; 41     for1(i,m)c[i]+=c[i-1]; 42     for3(i,n,0)sa[--c[x[i]]]=i; 43     for(int k=1;k<=n+1;k<<=1) 44     { 45         int p=0; 46         for2(i,n-k+1,n)y[p++]=i; 47         for0(i,n)if(sa[i]>=k)y[p++]=sa[i]-k; 48         for0(i,m)c[i]=0; 49         for0(i,n)c[x[y[i]]]++; 50         for1(i,m)c[i]+=c[i-1]; 51         for3(i,n,0)sa[--c[x[y[i]]]]=y[i]; 52         swap(x,y);p=0;x[sa[0]]=0; 53         for1(i,n)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p; 54         if(p>=n)break; 55         m=p; 56     } 57     for1(i,n)rk[sa[i]]=i; 58     for(int i=0,k=0,j;i<n;h[rk[i++]]=k) 59      for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++); 60 } 61 void gethash() 62 { 63     mi[0]=1; 64     for1(i,n)mi[i]=mi[i-1]*(ull)base; 65     for3(i,n-1,0)hash[i]=hash[i+1]*(ull)base+s[i]; 66 } 67 inline ull get(int x,int y){return hash[x]-hash[x+y]*mi[y];} 68 int main() 69 { 70     freopen("input.txt","r",stdin); 71     freopen("output.txt","w",stdout); 72     n=read();q=read(); 73     for0(i,n-1){char ch=getchar();while(ch<a||ch>z)ch=getchar();s[i]=ch-a+1;} 74     s[n]=0; 75     getsa(26); 76     for1(i,n)ed[i]=n-sa[i]-h[i]; 77     for1(i,n)ed[i]+=ed[i-1]; 78     gethash(); 79     while(q--) 80     { 81         ll x=read(),y=read(); 82         if(x<1||y<1||x>ed[n]||y>ed[n]){printf("-1\n");continue;} 83         ll t=lower_bound(ed+1,ed+n+1,x)-ed,l1=sa[t],r1=sa[t]+h[t]+x-ed[t-1]-1; 84         t=lower_bound(ed+1,ed+n+1,y)-ed;ll l2=sa[t],r2=sa[t]+h[t]+y-ed[t-1]-1; 85         int l=0,r=min(r1-l1+1,r2-l2+1); 86         while(l<=r) 87         { 88             int mid=(l+r)>>1; 89             if(get(l1,mid)==get(l2,mid))l=mid+1;else r=mid-1; 90         } 91         ll ans=(ll)r*(ll)r; 92         l=0,r=min(r1-l1+1,r2-l2+1); 93         while(l<=r) 94         { 95             int mid=(l+r)>>1; 96             if(get(r1-mid+1,mid)==get(r2-mid+1,mid))l=mid+1;else r=mid-1; 97         } 98         ans+=(ll)r*(ll)r; 99         printf("%lld\n",ans);100     }101     return 0;102 }
View Code

 

BZOJ3230: 相似子串