2015
09-17

# Reincarnation

Now you are back,and have a task to do:
Given you a string s consist of lower-case English letters only,denote f(s) as the number of distinct sub-string of s.
And you have some query,each time you should calculate f(s[l...r]), s[l...r] means the sub-string of s start from l end at r.

The first line contains integer T(1<=T<=5), denote the number of the test cases.
For each test cases,the first line contains a string s(1 <= length of s <= 2000).
Denote the length of s by n.
The second line contains an integer Q(1 <= Q <= 10000),denote the number of queries.
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n), denote a query.

The first line contains integer T(1<=T<=5), denote the number of the test cases.
For each test cases,the first line contains a string s(1 <= length of s <= 2000).
Denote the length of s by n.
The second line contains an integer Q(1 <= Q <= 10000),denote the number of queries.
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n), denote a query.

2
bbaba
5
3 4
2 2
2 5
2 4
1 4
baaba
5
3 3
3 4
1 4
3 5
5 5

3
1
7
5
8
1
3
8
5
1
Hint
I won't do anything against hash because I am nice.Of course this problem has a solution that don't rely on hash.


#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
const int N=5010;

struct State
{
State *pre,*go[26];
int step;
void clear()
{
pre=0;
step=0;
memset(go,0,sizeof(go));
}
int calc()
{
if(pre==0) return 0;
return step-pre->step;
}
}*root,*last;

State statePool[N*2],*cur;

void init()
{
cur=statePool;
root=last=cur++;
root->clear();
}

int tot;
void Insert(int w)
{
State *p=last;
State *np=cur++;
np->clear();
np->step=p->step+1;
while(p&&!p->go[w])
p->go[w]=np,p=p->pre;
if(p==0)
{
np->pre=root;
tot+=np->calc();
}
else
{
State *q=p->go[w];
if(p->step+1==q->step)
{
np->pre=q;
tot+=np->calc();
}
else
{
State *nq=cur++;
nq->clear();
memcpy(nq->go,q->go,sizeof(q->go));
tot-=p->calc()+q->calc();
nq->step=p->step+1;
nq->pre=q->pre;
q->pre=nq;
np->pre=nq;
tot+=p->calc()+q->calc()+np->calc()+nq->calc();
while(p&&p->go[w]==q)
p->go[w]=nq, p=p->pre;
}
}
last=np;
}

int ans[N][N];
char s[N];

void work()
{
scanf("%s",s);
int n=strlen(s);
for(int i=0;i<n;++i)
{
init();
tot=0;
for(int j=i;j<n;++j)
{
Insert(s[j]-'a');
ans[i][j]=tot;
}
}
int nQ;
scanf("%d", &nQ);
while (nQ--)
{
int l, r;
scanf("%d%d", &l, &r);
--l,--r;
printf("%d\n", ans[l][r]);
}
}

int main()
{
int T;
cin>>T;
while(T--)
work();
return 0;
}