Bzoj3230 相似子串

Time Limit: 20 Sec Memory Limit: 128 MB
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

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'组成

字符串后缀数组 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
",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
",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
");
131         else printf("%lld
",(LL)A[i][0]*A[i][0]+(LL)A[i][1]*A[i][1]); 
132     }
133     return 0;
134 }