代码

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
# define LL long long 
const int M = 1000005 ;
using namespace std ;

inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
    return x*w ;
}
char s[M] ;
int n , m , b[M] , pos[M] ;
int c[M] , val[M] , tot , rt[M] , idl , idr ;

struct Suffix {
    int Last , cnt , size[M] ;
    int fa[M] , st[M] , son[M][26] ;
    inline void Init() {
        for(int i = 1 ; i <= cnt ; i ++) {
            for(int j = 0 ; j < 26 ; j ++)  son[i][j] = 0 ;
            size[i] = fa[i] = st[i] = pos[i] = val[i] = 0 ;
        }
        Last = cnt = 1 ;
    }
    inline void Insert(int c) {
        int p = Last , np = ++ cnt ; 
        Last = np ; st[np] = st[p] + 1 ; size[np] = 1 ;
        while(p && !son[p][c]) son[p][c] = np , p = fa[p] ;
        if(!p) fa[np] = 1 ;
        else {
            int q = son[p][c] ;
            if(st[q] == st[p] + 1) fa[np] = q ;
            else {
                int nq = ++ cnt ; st[nq] = st[p] + 1 ;
                memcpy(son[nq] , son[q] , sizeof(son[q])) ;
                fa[nq] = fa[q] ; fa[np] = fa[q] = nq ;
                while(son[p][c] == q) son[p][c] = nq , p = fa[p] ;
            }
        }
    }
    inline void Sort() {
        for(int i = 1 ; i <= cnt ; i ++) ++ c[st[i]] ;
        for(int i = 2 ; i <= cnt ; i ++) c[i] += c[i - 1] ;
        for(int i = 1 ; i <= cnt ; i ++) b[c[st[i]] --] = i ;
        for(int i = cnt , p ; i >= 1 ; i --) {
            p = b[i] ;
            if(!pos[fa[p]]) pos[fa[p]] = pos[p] ;
            else pos[fa[p]] = min(pos[fa[p]] , pos[p]) ;
        }
        for(int i = 1 ; i <= cnt ; i ++) c[i] = b[i] = 0 ;
    }
} S1 , S2 ;

namespace F_Tree {
    # define ls t[now].l
    # define rs t[now].r
    struct Node { int l , r , size ; } t[M * 25] ;
    void Build(int x , int l , int r , int &now) {
        if(!now) now = ++ tot ; t[now].size ++ ;
        if(l == r) return ; int mid = (l + r) >> 1 ;
        if(mid >= x) Build(x , l , mid , ls) ; else Build(x , mid + 1 , r , rs) ;
    }
    int Merge(int x , int y , int l , int r) {
        if(!x || !y) return x + y ; int ecnt = ++ tot ;
        t[ecnt].size = t[x].size + t[y].size ; 
        if(l == r) return ecnt ; int mid = (l + r) >> 1 ; 
        t[ecnt].l = Merge(t[x].l , t[y].l , l , mid) ; 
        t[ecnt].r = Merge(t[x].r , t[y].r , mid + 1 , r) ;
        return ecnt ;
    }
    int query(int L , int R , int l , int r , int now) {
        if(!now || l > R || r < L) return 0 ; 
        if(l == L && r == R) return t[now].size ;
        int mid = (l + r) >> 1 ;
        if(mid >= R) return query(L , R , l , mid , ls) ;
        if(mid < L) return query(L , R , mid + 1 , r , rs) ;
        else return query(L , mid , l , mid , ls) + query(mid + 1 , R , mid + 1 , r , rs) ;
    }
    # undef ls
    # undef rs
}
using namespace F_Tree ;
inline LL Solve() {
    LL Ans = 0 ; int temp = 0 , p = 1 ;
    for(int i = 1 , c ; i <= m ; i ++) {
        c = s[i] - 'a' ;
        while(1) {
        	if(S1.son[p][c] && query(idl + temp , idr , 1 , n , rt[S1.son[p][c]])) {
        		p = S1.son[p][c] ;
        		++ temp ; break ;
            }
            if(!temp) { p = 1 ; break ; }
            -- temp ;
            if(temp == S1.st[S1.fa[p]]) p = S1.fa[p] ;
        }
        val[i] = temp ;
    }
    S2.Sort() ;
    for(int i = 2 ; i <= S2.cnt ; i ++)
        Ans += max(S2.st[i] - max(S2.st[S2.fa[i]] , val[pos[i]]) , 0) ;
    return Ans ;
}
int main() {
    scanf("%s",s + 1) ; n = strlen(s + 1) ; S1.Init() ; 
    for(int i = 1 ; i <= n ; i ++) {
        S1.Insert(s[i] - 'a') ;
        Build(i , 1 , n , rt[S1.Last]) ;
    }
    for(int i = 1 ; i <= S1.cnt ; i ++) ++c[S1.st[i]] ;
    for(int i = 2 ; i <= S1.cnt ; i ++) c[i] += c[i - 1] ;
    for(int i = 1 ; i <= S1.cnt ; i ++) b[c[S1.st[i]] --] = i ;
    for(int i = S1.cnt , p ; i >= 1 ; i --) {
        p = b[i] ;
        if(S1.fa[p]) rt[S1.fa[p]] = Merge(rt[S1.fa[p]] , rt[p] , 1 , n) ;
    }
    memset(c , 0 , sizeof(c)) ;
    int Q = read() ;
    while(Q --) {
        scanf("%s",s + 1) ; m = strlen(s + 1) ; idl = read() ; idr = read() ;
        S2.Init() ; for(int i = 1 ; i <= m ; i ++) S2.Insert(s[i] - 'a') , pos[S2.Last] = i ;
        printf("%lld\n",Solve()) ;
    }
    return 0 ;
}

评测结果