首页 > 代码库 > Bzoj3230 相似子串
Bzoj3230 相似子串
Submit: 1783 Solved: 444
[Submit][Status][Discuss]
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
ababa
3 5
5 9
8 10
Sample Output
18
16
-1
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‘组成
字符串 后缀数组 ST表
哇，我可能是写了假的ST表，下标错了一位，WA到飞起
先算出后缀数组，然后按rank递增顺序维护本质不同的子串的数量的前缀和（显然rank为i的串长度减去height[i]就是这个串贡献出的不同子串数量），然后可以在前缀和数组上二分，找到第X个本质不同子串的起点所在的后缀的rank（好绕口），记为id。那么目标串的起点就是sa[id]，终点就是 sa[id]+height[id]-1+(X-sum[id-1])。
成功对两个目标串定位以后，分别求最长公共前缀和后缀长度，它们平方的和就是答案
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=100010; 9 LL read(){ 10 LL x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 int sa[mxn],rk[mxn],ht[mxn],r[mxn]; 16 LL smm[mxn]; 17 int wa[mxn],wb[mxn],wv[mxn],cnt[mxn]; 18 inline int cmp(int *r,int a,int b,int l){ 19 return r[a]==r[b] && r[a+l]==r[b+l]; 20 } 21 void GetSA(int *sa,int n,int m){ 22 int *x=wa,*y=wb; 23 int i,j,p; 24 for(i=0;i<m;i++)cnt[i]=0; 25 for(i=0;i<n;i++)cnt[x[i]=r[i]]++; 26 for(i=1;i<m;i++)cnt[i]+=cnt[i-1]; 27 for(i=n-1;i>=0;i--)sa[--cnt[x[i]]]=i; 28 for(j=1,p=0;p<n;j<<=1,m=p){ 29 p=0;for(i=n-j;i<n;i++)y[p++]=i; 30 for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j; 31 for(i=0;i<m;i++)cnt[i]=0; 32 for(i=0;i<n;i++)++cnt[x[y[i]]]; 33 for(i=1;i<m;i++)cnt[i]+=cnt[i-1]; 34 for(i=n-1;i>=0;i--)sa[--cnt[x[y[i]]]]=y[i]; 35 swap(x,y); 36 p=1;x[sa[0]]=0; 37 for(i=1;i<n;i++) 38 x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++; 39 } 40 return; 41 } 42 void GetHT(int n){ 43 int i,j,k=0; 44 for(i=1;i<=n;i++)rk[sa[i]]=i; 45 for(i=0;i<n;i++){ 46 if(k)k--; 47 j=sa[rk[i]-1]; 48 while(r[i+k]==r[j+k])k++; 49 ht[rk[i]]=k; 50 } 51 smm[0]=0; 52 for(i=1;i<=n;i++)smm[i]=smm[i-1]+n-sa[i]-ht[i]; 53 return; 54 } 55 int f[mxn][18],lg[mxn]; 56 int n,Q; 57 void ST_init(){ 58 for(int i=1;i<=n;i++)f[i][0]=ht[i]; 59 for(int j=1;j<18;j++) 60 for(int i=1;i<=n;i++){ 61 if(i+(1<<j)-1>n)break; 62 f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]); 63 } 64 return; 65 } 66 int ST(int x,int y){ 67 if(x>y)swap(x,y);++x; 68 int tmp=lg[y-x+1]; 69 return min(f[x][tmp],f[y-(1<<tmp)+1][tmp]); 70 } 71 struct QUE{ 72 LL x,y; 73 int s1,t1,s2,t2; 74 }q[mxn]; 75 LL A[mxn][2]; 76 int calc(LL x,LL y,int ID){ 77 int id=lower_bound(smm+1,smm+n+1,x)-smm; 78 int s1=sa[id]; 79 int t1=s1+(LL)ht[id]-1+x-smm[id-1]; 80 id=lower_bound(smm+1,smm+n+1,y)-smm; 81 int s2=sa[id]; 82 int t2=s2+(LL)ht[id]-1+y-smm[id-1]; 83 q[ID].s1=s1;q[ID].t1=t1;q[ID].s2=s2;q[ID].t2=t2; 84 int res=min(t1-s1+1,t2-s2+1); 85 if(s1!=s2)res=min(res,ST(rk[s1],rk[s2]));//printf("res:%d\n",res); 86 return res; 87 } 88 int calc2(int ID){ 89 int s1=q[ID].s1;int t1=q[ID].t1; 90 int s2=q[ID].s2;int t2=q[ID].t2; 91 int res=min(t1-s1+1,t2-s2+1); 92 if(s1!=s2)res=min(res,ST(rk[s1],rk[s2]));//printf("res:%d\n",res); 93 return res; 94 } 95 void solve(int id){ 96 GetSA(sa,n+1,28); 97 GetHT(n); 98 ST_init(); 99 for(int i=1;i<=Q;i++){100 if(q[i].x>0 && q[i].x<=smm[n] && q[i].y>0 && q[i].y<=smm[n]){101 // if(q[i].x<=smm[n] && q[i].y<=smm[n]){102 if(!id)A[i][id]=calc(q[i].x,q[i].y,i);103 else A[i][id]=calc2(i);104 }105 else A[i][id]=-1;106 }107 return;108 }109 char s[mxn];110 int main(){111 // freopen("in.txt","r",stdin);112 int i,j;113 n=read();Q=read();114 scanf("%s",s);115 for(i=1;i<=Q;i++){116 q[i].x=read();q[i].y=read();117 }118 lg[0]=-1;119 for(i=1;i<=n;i++)lg[i]=lg[i>>1]+1;120 for(i=0;i<n;i++)r[i]=s[i]-‘a‘+1;121 solve(0);122 reverse(r,r+n);123 for(i=1;i<=Q;i++){124 q[i].s1=n-q[i].s1-1;q[i].s2=n-q[i].s2-1;125 q[i].t1=n-q[i].t1-1;q[i].t2=n-q[i].t2-1;126 swap(q[i].s1,q[i].t1);swap(q[i].s2,q[i].t2);127 }128 solve(1);129 for(i=1;i<=Q;i++){130 if(A[i][0]==-1)printf("-1\n");131 else printf("%lld\n",(LL)A[i][0]*A[i][0]+(LL)A[i][1]*A[i][1]); 132 }133 return 0;134 }
Bzoj3230 相似子串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。