试题描述

输入一个字符串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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #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=0,f=1;char c=getchar();    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) x=x*10+c-'0';    return x*f;}const int maxn=200010;int n,od[maxn],x[maxn],f[maxn];int to[maxn][26],fa[maxn],l[maxn],pos[maxn],cnt=1,last=1;void extend(int c,int id) {    int p=last,q,np,nq;    l[pos[id]=last=np=++cnt]=l[p]+1;f[np]=1;    for(;!to[p][c];p=fa[p]) to[p][c]=np;    if(!p) fa[np]=1;    else {        q=to[p][c];        if(l[p]+1==l[q]) fa[np]=q;        else {            l[nq=++cnt]=l[p]+1;            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][23];void dfs(int x) {    anc[x][0]=fa[x];    rep(1,22) anc[x][i]=anc[anc[x][i-1]][i-1];    ren dfs(To[i]);}void init() {    rep(1,cnt) AddEdge(fa[i],i);    dfs(1);    rep(1,cnt) x[l[i]]++;    rep(1,n) x[i]+=x[i-1];    rep(1,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=22;i>=0;i--) if(R-L+1<=l[anc[p][i]]) p=anc[p][i];    return f[p];}char s[maxn];int main() {    scanf("%s",s);n=strlen(s);    rep(0,n-1) extend(s[i]-'a',i+1);    init();    int m=read();    while(m--) {        int l=read(),r=read();        printf("%d\n",solve(l,r));    }    return 0;}