一眼似乎不可做，但发现\(strlen(x)\)很小，暴力\(O(n^2)\)预处理每个区间\((l,r)\)，查询时\(O(1)\)输出就好了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         typedef int LL;const LL maxn=2010;inline LL Read(){    LL x=0,f=1; char c=getchar();    while(c<'0'||c>'9'){        if(c=='-') f=-1; c=getchar();    }    while(c>='0'&&c<='9')        x=(x<<3)+(x<<1)+c-'0',c=getchar();    return x*f;}struct node{    LL len,fail;    LL son[26];}t[maxn<<1];LL n,m,T,nod,last;LL ans[maxn][maxn];char s[maxn];inline void Insert(LL c){    LL np=++nod,p=last;    last=np;    t[np].len=t[p].len+1;    while(p&&!t[p].son[c]){        t[p].son[c]=np,        p=t[p].fail;    }    if(!p)        t[np].fail=1;    else{        LL q=t[p].son[c];        if(t[q].len==t[p].len+1)            t[np].fail=q;        else{            LL nq=++nod;            t[nq]=t[q];            t[nq].len=t[p].len+1;            t[np].fail=t[q].fail=nq;            while(p&&t[p].son[c]==q){                t[p].son[c]=nq,                p=t[p].fail;            }        }    }}int main(){    T=Read();    while(T--){        scanf(" %s",s+1);        LL Len=strlen(s+1);        for(LL i=1;i<=Len;++i){            nod=last=1;            memset(t,0,sizeof(t));            for(LL j=i;j<=Len;++j){                Insert(s[j]-'a'),                ans[i][j]=ans[i][j-1]+t[last].len-t[t[last].fail].len;            }        }        m=Read();        while(m--){            LL l=Read(),r=Read();            printf("%d\n",ans[l][r]);        }    }    return 0;}