|
e(c < '0' || c > '9') ;
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
if(a >= 10)OT(a / 10) ;
putchar(a % 10 + '0') ;
}
struct SAM {
SAM*pre ,*next[26] ;
int val ;
void clear() {
pre = 0 ;
val = 0 ;
mem(next ,0) ;
}
} ;
SAM *root ,*last ,*cur ;
SAM qe[111111] ;
int cnt = 0 ;
void init() {
cnt = 0 ;
root = last = &qe[cnt ++] ;
root -> clear() ;
}
struct QU{
int s ,e ,id ;
}QQ[100005] ;
void extend(int w ) {
SAM*p = last ;
SAM*np = &qe[cnt ++] ;
np -> clear() ;
np -> val = p -> val + 1 ;
while(p && !p -> next[w] )p -> next[w] = np ,p = p -> pre ;
if(!p) {
np -> pre = root ;
} else {
SAM *q = p -> next[w] ;
if(p -> val + 1 == q -> val) {
np -> pre = q ;
} else {
SAM *nq = &qe[cnt ++] ;
nq -> clear() ;
memcpy(nq -> next ,q -> next ,sizeof(q -> next)) ;
nq -> val = p -> val + 1 ;
nq -> pre = q -> pre ;
q -> pre = nq ;
np -> pre = nq ;
while(p && p -> next[w] == q) {
p -> next[w] = nq ;
p = p -> pre ;
}
}
}
last = np ;
}
#define N 100005
#define M 2005
char a[M] ;
bool cmp(QU a ,QU b){
if(a.s == b.s)return a.e < b.e ;
return a.s < b.s ;
}
int solve(){
int sum = 0 ;
for (int i = cnt - 1 ; i > 0 ; i -- ){
sum += qe[i].val - qe[i].pre -> val ;
}
return sum ;
}
int ans[N] ;
int main() {
int T ;
cin >> T ;
while( T -- ) {
cin >> a ;
mem(ans, 0) ;
int l = strlen(a) ;
int Q ;
cin >> Q ;
for (int i = 0 ; i < Q ; i ++ ){
RD(QQ[i].s) ;
RD(QQ[i].e) ;
QQ[i].s -- ;
QQ[i].e -- ;
QQ[i].id = i ;
}
sort(QQ , QQ + Q , cmp) ;
init() ;
int st = QQ[0].s ;
int ed = QQ[0].e ;
for (int i = st ; i <= ed ; i ++ ){
extend(a[i] - 'a') ;
}
for (int i = cnt - 1 ; i > 0 ; i -- ){
ans[QQ[0].id] += qe[i].val - qe[i].pre -> val ;
}
for (int i = 1 ; i < Q ;i ++ ){
// cout << QQ[i].s << " " << QQ[i].e << endl;
// getchar() ;
if(QQ[i].s != QQ[i - 1].s){
init() ;
for (int j = QQ[i].s ; j <= QQ[i].e ; j ++ )extend(a[j] - 'a' ) ;
ans[QQ[i].id] = solve() ;
}
else {
if(QQ[i].e == QQ[i - 1].e){
ans[QQ[i].id] = ans[QQ[i - 1].id] ;
}else{
for (int j = ed + 1 ; j <= QQ[i].e ; j ++ )extend(a[j] - 'a' ) ;
ans[QQ[i].id] = solve() ;
}
}
ed = QQ[i].e ;
}
for (int i = 0 ; i < Q ;i ++ ){
OT(ans[i]) ;
puts("") ;
}
}
return 0 ;
}
|