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）查询。
作为蒟蒻我写了后一种。。。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 150000+5
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define ull unsigned long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
#define base 13131
using namespace std;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,q,s[maxn],t[maxn],t2[maxn],c[maxn],sa[maxn],rk[maxn],h[maxn];
ll ed[maxn];
ull hash[maxn],mi[maxn];
void getsa(int m)
{
int *x=t,*y=t2;
for0(i,m)c[i]=;
for0(i,n)c[x[i]=s[i]]++;
for1(i,m)c[i]+=c[i-];
for3(i,n,)sa[--c[x[i]]]=i;
for(int k=;k<=n+;k<<=)
{
int p=;
for2(i,n-k+,n)y[p++]=i;
for0(i,n)if(sa[i]>=k)y[p++]=sa[i]-k;
for0(i,m)c[i]=;
for0(i,n)c[x[y[i]]]++;
for1(i,m)c[i]+=c[i-];
for3(i,n,)sa[--c[x[y[i]]]]=y[i];
swap(x,y);p=;x[sa[]]=;
for1(i,n)x[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]?p:++p;
if(p>=n)break;
m=p;
}
for1(i,n)rk[sa[i]]=i;
for(int i=,k=,j;i<n;h[rk[i++]]=k)
for(k?k--:,j=sa[rk[i]-];s[i+k]==s[j+k];k++);
}
void gethash()
{
mi[]=;
for1(i,n)mi[i]=mi[i-]*(ull)base;
for3(i,n-,)hash[i]=hash[i+]*(ull)base+s[i];
}
inline ull get(int x,int y){return hash[x]-hash[x+y]*mi[y];}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();q=read();
for0(i,n-){char ch=getchar();while(ch<'a'||ch>'z')ch=getchar();s[i]=ch-'a'+;}
s[n]=;
getsa();
for1(i,n)ed[i]=n-sa[i]-h[i];
for1(i,n)ed[i]+=ed[i-];
gethash();
while(q--)
{
ll x=read(),y=read();
if(x<||y<||x>ed[n]||y>ed[n]){printf("-1\n");continue;}
ll t=lower_bound(ed+,ed+n+,x)-ed,l1=sa[t],r1=sa[t]+h[t]+x-ed[t-]-;
t=lower_bound(ed+,ed+n+,y)-ed;ll l2=sa[t],r2=sa[t]+h[t]+y-ed[t-]-;
int l=,r=min(r1-l1+,r2-l2+);
while(l<=r)
{
int mid=(l+r)>>;
if(get(l1,mid)==get(l2,mid))l=mid+;else r=mid-;
}
ll ans=(ll)r*(ll)r;
l=,r=min(r1-l1+,r2-l2+);
while(l<=r)
{
int mid=(l+r)>>;
if(get(r1-mid+,mid)==get(r2-mid+,mid))l=mid+;else r=mid-;
}
ans+=(ll)r*(ll)r;
printf("%lld\n",ans);
}
return ;
}