题目链接：戳我
因为对应的很多询问，所以我们一定要将每一种询问先处理出来，然后O(1)查询。
至于怎么处理出来子串的子串呢？
我们固定左端点，然后依次加入子串即可。然后统计的时候直接统计last那一个类的即可（因为只有last是真正新建出来的节点，多出来的本质不同的子串也是出现在这里面的），我们直接(t[i].longest-t[i].shortest+1=t[i].len-t[t[i].ff].len)即可。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 2010
using namespace std;
int last=1,tot=1,T,len,n,m;
int ans[MAXN][MAXN];
char s[MAXN];
struct Node{int len,ff,ch[26];}t[MAXN<<1];
inline void extend(int c)
{
int p=last,np=++tot;last=np;
t[np].len=t[p].len+1;
while(p&&!t[p].ch[c]) t[p].ch[c]=np,p=t[p].ff;
if(!p) t[np].ff=1;
else
{
int q=t[p].ch[c];
if(t[q].len==t[p].len+1) t[np].ff=q;
else
{
int nq=++tot;
t[nq]=t[q],t[nq].len=t[p].len+1;
t[np].ff=t[q].ff=nq;
while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].ff;
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
memset(ans,0,sizeof(ans));
last=tot=1;
scanf("%s",s+1);
len=strlen(s+1);
for(int i=1;i<=len;i++)
{
memset(t,0,sizeof(t));
tot=last=1;
for(int j=i;j<=len;j++)
{
extend(s[j]-'a'+1);
ans[i][j]=ans[i][j-1]+t[last].len-t[t[last].ff].len;
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d
",ans[l][r]);
}
}
return 0;
}