1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
#define MID(x,y) ((x+y)>>1)
#define maxn 2205
#define print() cout<<"------------"<<endl
using namespace std;
char s[20005];
unsigned int hash[maxn],ans[maxn][maxn],h[maxn][maxn];
int seed=13;
pair<int,int> pa[maxn];
int q,n,m;
int binsearch(int val,int l,int r){
while (l <= r){
int mid = MID(l,r);
if(hash[mid] == val) return mid;
else if(hash[mid] < val) return binsearch(val,mid+1,r);
else return binsearch(val,l,mid-1);
}
}
int main (){
int t,l,r;
cin>>t;
while (t--){
cin>>s;
n = strlen(s);
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
ans[i][j] = 0;
for (int i = 0; i < n; ++i){
int val = 0;
for (int j = i; j < n; ++j){
val = val * seed + s[j];
h[i][j] = (val & 0x7FFFFFFF);
}
}
for (int len = 1; len <= n; len++){
m = 0;
for(int i = 0; i < n-len+1; ++i){
hash[m++] = h[i][i+len-1];
}
sort(hash,hash+m);
int tmp = 0;
for (int i = 1; i < m; ++i)
if(hash[tmp] != hash[i])
hash[++tmp] = hash[i];
m = tmp +1;
for (int i = 0;i < m; ++i)
pa[i] = make_pair(-1,-1);
for (int i = 0; i < n-len+1; ++i)
{
int val = h[i][i+len-1];
int pos = binsearch(val,0,m-1);
r = i + len - 1;
int le1 = -1,le2 = i + 1;
le1 = pa[pos].first+1;
ans[le1][r] ++;
ans[le2][r] --;
pa[pos] = make_pair(i,i+len-1);
}
}
for (int i = 0; i < n; ++i)
for (int j = 1; j < n; ++j)
ans[i][j] += ans[i][j-1];
for (int j = 0; j < n; ++j)
for (int i = 1; i < n; ++i)
ans[i][j] += ans[i-1][j];
cin>>q;
for (int i = 0; i < q; ++i)
{
scanf("%d%d", &l, &r);
l--;r--;
printf("%dn", ans[l][r]);
}
}
return 0;
}
|