一眼似乎不可做，但发现(strlen(x))很小，暴力(O(n^2))预处理每个区间((l,r))，查询时(O(1))输出就好了
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
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
",ans[l][r]);
}
}
return 0;
}