|
试题描述
|
|
输入一个字符串S，回答Q次问题，给你l,r，输出从Sl--Sr组成的串在S中出现了多少次。 |
|
输入
|
|
第一行为一个字符串S。
第二行为一个正整数Q。 接下来Q行每行为l,r。 |
|
输出
|
|
对于每个询问，输出答案。
|
|
输入示例
|
|
ababaaabab
5 1 1 2 3 2 2 2 4 1 4 |
|
输出示例
|
|
6
3 4 2 2 |
|
其他说明
|
|
1<=l<=r<=|S|<=100000
1<=Q<=1000000 保证S由26个小写字母组成 |
考虑用后缀自动机来水此题
复习一下SAM，每个结束态S的祖先与S构成了S最长串的所有后缀。
SAM的每个节点表示的串长度在(l[fa[x]],l[x]]之间，因此我们可以倍增来求最上方符合条件的节点，预处理每个节点end-set集的大小，就可以O((|S|+Q)logn)解决此题了
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,od[maxn],x[maxn],f[maxn];
int to[maxn][],fa[maxn],l[maxn],pos[maxn],cnt=,last=;
void extend(int c,int id) {
int p=last,q,np,nq;
l[pos[id]=last=np=++cnt]=l[p]+;f[np]=;
for(;!to[p][c];p=fa[p]) to[p][c]=np;
if(!p) fa[np]=;
else {
q=to[p][c];
if(l[p]+==l[q]) fa[np]=q;
else {
l[nq=++cnt]=l[p]+;
memcpy(to[nq],to[q],sizeof(to[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;to[p][c]==q;p=fa[p]) to[p][c]=nq;
}
}
}
int first[maxn],next[maxn],To[maxn],e;
void AddEdge(int u,int v) {
To[++e]=v;next[e]=first[u];first[u]=e;
}
int anc[maxn][];
void dfs(int x) {
anc[x][]=fa[x];
rep(,) anc[x][i]=anc[anc[x][i-]][i-];
ren dfs(To[i]);
}
void init() {
rep(,cnt) AddEdge(fa[i],i);
dfs();
rep(,cnt) x[l[i]]++;
rep(,n) x[i]+=x[i-];
rep(,cnt) od[x[l[i]]--]=i;
for(int i=cnt;i;i--) f[fa[od[i]]]+=f[od[i]];
}
int solve(int L,int R) {
int p=pos[R];
for(int i=;i>=;i--) if(R-L+<=l[anc[p][i]]) p=anc[p][i];
return f[p];
}
char s[maxn];
int main() {
scanf("%s",s);n=strlen(s);
rep(,n-) extend(s[i]-'a',i+);
init();
int m=read();
while(m--) {
int l=read(),r=read();
printf("%d\n",solve(l,r));
}
return ;
}