C++(g++ 7.5.0) 解法, 执行用时: 366ms, 内存消耗: 97484K, 提交时间: 2023-04-14 15:07:31

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5;
char s[N];

int tot=1,fa[N<<1],len[N<<1],ch[N<<1][26];
int last=1,p,np,q,nq;
int ri[N<<1];
int v[N<<1],sa[N<<1];
int st[N][19],id[N];
void extend(int c,int k)
{
    len[np=++tot]=len[last]+1;
    for(p=last;p && !ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else
    {
        q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else
        {
            len[nq=++tot]=len[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[nq]));
            fa[nq]=fa[q];
            fa[q]=fa[np]=nq;
            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
    
    last=np;
    ri[last]=1;
    id[k]=last;
}
int query(int l,int r)
{
	int u=id[r];
	for(int i=18;i>=0;i--)
		if(len[st[u][i]]>=r-l+1) u=st[u][i];
	return ri[u];
}
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;++i) extend(s[i]-'a',i);
    for(int i=1;i<=tot;++i) st[i][0]=fa[i];
    for(int i=1;i<=tot;++i) v[len[i]]++;
    for(int i=1;i<=n;++i) v[i]+=v[i-1];
    for(int i=1;i<=tot;++i) sa[v[len[i]]--]=i;
    for(int i=tot;i;--i) ri[fa[sa[i]]]+=ri[sa[i]];
    for(int j=1;j<=18;j++)
    	for(int i=1;i<=tot;i++)
    		st[i][j]=st[st[i][j-1]][j-1];
    int q;scanf("%d",&q);
    while(q--) 
    {
    	int l,r;scanf("%d%d",&l,&r);
    	printf("%d\n",query(l,r));
	}
}