【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=4622
【题目大意】
给出一个长度不超过2000的字符串，有不超过10000个询问，问【L，R】子串中出现的子串数目，相同子串不可重复计数。
【题解】
考虑到字符串长度只有两千，我们对每个位置往后建立2000个后缀自动机，
这样子就能分别计算每个位置往后出现的字符串数目并保存，
对于sam上的一个节点来说，它的匹配长度与失配位置的匹配长度只差就是他们之间的子串，
所以，我们在建立sam可以同时计算出现的子串数目。
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=4005;
char s[N];
struct sam{
int p,q,np,nq,cnt,last,tot,a[N][26],l[N],f[N];
sam(){tot=cnt=0;last=++cnt;}
int val(int c){return l[c]-l[f[c]];}
void init(){
tot=cnt=0;last=++cnt;
memset(a,0,sizeof(a));
memset(l,0,sizeof(l));
memset(f,0,sizeof(f));
}
int val(int c){return l[c]-l[f[c]];}
void extend(int c){
p=last;np=last=++cnt;l[np]=l[p]+1;
while(!a[p][c]&&p)a[p][c]=np,p=f[p];
if(!p){f[np]=1;tot+=val(np);}
else{
q=a[p][c];
if(l[p]+1==l[q]){f[np]=q;tot+=val(np);}
else{
nq=++cnt;l[nq]=l[p]+1;
memcpy(a[nq],a[q],sizeof(a[q]));
tot-=val(p)+val(q);
f[nq]=f[q]; f[np]=f[q]=nq;
tot+=val(p)+val(q)+val(np)+val(nq);
while(a[p][c]==q)a[p][c]=nq,p=f[p];
}
}
}int ans[2005][2005];
void CalAns(){
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=1;i<=len;i++){
init();
for(int j=i;j<=len;j++){
extend(s[j]-'a');
ans[i][j]=tot;
}
}
}
void solve(){
int Q,l,r;
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&l,&r);
printf("%d\n",ans[l][r]);
}
}
}sam;
int main(){
int T;
scanf("%d",&T);
while(T--){
sam.CalAns();
sam.solve();
}return 0;
}