3230: 相似子串
Time Limit: 20 Sec Memory Limit: 128 MB
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'组成
题解： 首先我们要解决的是本质不同的子串计数问题:
考虑到子串一定是后缀的前缀,我们按照rank顺序添加每个后缀,
那么每添加一个新后缀就会产生n-sa+1个新的前缀(子串)
但是由于lcp的存在,这些子串又和前面的那一串重复的一些
所以最后的计算式是Σn-sa+1-height,当然具体的细节,诸如±1会随代码风格和计算方式略有不同,读者自行修改即可
接着我们考虑,本题其实就是让我们求某两个子串最长公共前缀和最长公共后缀
这样我们可以跑一个SA之后把字串反转再求一套,我们就得到了后缀数组和一个诡异的"前缀数组"
接着我们二分找到子串对应的端点以及后缀,再用rmq求一下lcp区间最小值即可.
代码实现(当时我调到意识模糊于是封装了一下233):
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=;
int n,xx[N],yy[N],cnt[N],bin[];
LL num[N];
struct Fleet
{
int sa[N],height[N],rank[N],f[N][];
char s[N];
int i,j,k,p,m;
inline void get_sa()
{
int *x=xx,*y=yy;m=;
for(i=;i<m;++i)cnt[i]=;
for(i=;i<n;++i)++cnt[x[i]=s[i]];
for(i=;i<m;++i)cnt[i]+=cnt[i-];
for(i=n-;~i;--i)sa[--cnt[x[i]]]=i;
for(k=,p=;p<n&&k<=n;k<<=,m=p)
{
for(p=,i=n-k;i<n;++i)y[p++]=i;
for(i=;i<n;++i)if(sa[i]>=k)y[p++]=sa[i]-k;
for(i=;i<m;++i)cnt[i]=;
for(i=;i<n;++i)++cnt[x[y[i]]];
for(i=;i<m;++i)cnt[i]+=cnt[i-];
for(i=n-;~i;--i)sa[--cnt[x[y[i]]]]=y[i];
for(swap(x,y),p=,x[sa[]]=,i=;i<n;++i)
x[sa[i]]=(y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k])?p-:p++;
}
}
inline void get_rank()
{
for(i=;i<n;++i)rank[sa[i]]=i;
for(k=i=;i<n;height[rank[i++]]=k)
for(k=k?k-:k,j=sa[rank[i]-];s[i+k]==s[j+k];++k);
}
inline void ST()
{
for(i=;i<n;++i)f[i][]=height[i];
for(i=;bin[i]<=n;++i)
for(j=;j+bin[i]-<n;++j)
f[j][i]=min(f[j][i-],f[j+bin[i-]][i-]);
}
inline LL query(int l,int r)
{
int len=r-l+,k=;
while(bin[k+]<=len)++k;
return min(f[l][k],f[r-bin[k]+][k]);
}
inline void get_kth(int &st,int &ed,LL rk)
{
int ans=lower_bound(num,num+n,rk)-num;
st=sa[ans],ed=st+height[ans]-+rk-num[ans-];
}
inline void intn()
{get_sa(),get_rank(),ST();}
inline void calc()
{for(i=;i<n;++i)num[i]=num[i-]+LL(n-sa[i]-height[i]-);}
}Sfx,Pre;
inline LL get_length(LL id1,LL id2)
{
register int i,j,k,st[],ed[];
Sfx.get_kth(st[],ed[],id1);
Sfx.get_kth(st[],ed[],id2);
LL val=min(ed[]+1ll-st[],ed[]+1ll-st[]),tmp=val;
if(st[]!=st[])
if(Sfx.rank[st[]]<Sfx.rank[st[]])
tmp=min(tmp,Sfx.query(Sfx.rank[st[]]+,Sfx.rank[st[]]));
else
tmp=min(tmp,Sfx.query(Sfx.rank[st[]]+,Sfx.rank[st[]]));
ed[]=n--ed[],ed[]=n--ed[];
if(ed[]!=ed[])
if(Pre.rank[ed[]]<Pre.rank[ed[]])
val=min(val,Pre.query(Pre.rank[ed[]]+,Pre.rank[ed[]]));
else
val=min(val,Pre.query(Pre.rank[ed[]]+,Pre.rank[ed[]]));
return tmp*tmp+val*val;
}
int main()
{
register int i,j,m,a,b,q;LL u,v;
scanf("%d%d%s",&n,&m,Sfx.s);
for(bin[]=i=;i<=;++i)bin[i]=bin[i-]<<;
for(i=;i<=n;++i)Pre.s[i-]=Sfx.s[n-i];
Sfx.s[n]=Pre.s[n]=,n++;
Sfx.intn();Pre.intn();Sfx.calc();
while(m--)
{
scanf("%lld%lld",&u,&v);
if(u>num[n-]||v>num[n-])printf("-1\n");
else printf("%lld\n",get_length(u,v));
}
}