代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
# define LL long long
const int M = 1600000 ;
const int N = 100005 ;
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 tmp[M] ;
int Fn , n , qnum , ret , s[M] ;
struct Node {
    int l , r , sum ;
} t[M * 24] ;
struct Ques {
    int len ,stp , l , r ;
} q[N] ;
namespace SA {
    int m , a[M] , b[M] , c[M] ;
    int sa[M] , rnk[M] , lg[M] , h[M] , st[M][25] ;
    inline void Qsort() {
        memset(c , 0 , sizeof(c)) ;
        for(int i = 1 ; i <= n ; i ++) ++ c[a[i]] ;
        for(int i = 2 ; i <= m ; i ++) c[i] += c[i - 1] ;
        for(int i = n ; i >= 1 ; i --) sa[c[a[b[i]]] --] = b[i] ;
    } 
    inline void Make_SA() {
        for(int i = 1 ; i <= n ; i ++) a[i] = s[i] , b[i] = i ;
        m = 200000 ; Qsort() ;
        for(int k = 1 ; k <= n ; k <<= 1) {
            int Num = 0 ;
            for(int i = n - k + 1 ; i <= n ; i ++) b[++Num] = i ;
            for(int i = 1 ; i <= n ; i ++)
                if(sa[i] > k)
                    b[++Num] = sa[i] - k ;
            Qsort() ; swap(a , b) ;
            a[sa[1]] = 1 ; Num = 1 ;
            for(int i = 2 ; i <= n ; i ++)
                a[sa[i]] = (b[sa[i]] == b[sa[i - 1]] && b[sa[i] + k] == b[sa[i - 1] + k]) ? Num : ++ Num ;
            if(Num == n) break ;
            m = Num ;
        }
    }
    inline void Build() {
        int k = 0 ;
        for(int i = 1 ; i <= n ; i ++) rnk[sa[i]] = i ;
        for(int i = 2 ; i <= n ; i ++) lg[i] = lg[i >> 1] + 1 ;
        for(int i = 1 ; i <= n ; i ++) {
            if(rnk[i] == 1) continue ;
            if(k) -- k ;
            int j = sa[rnk[i] - 1] ;
            while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++ k ;
            h[rnk[i]] = k ;
        }
        for(int i = 1 ; i <= n ; i ++) st[i][0] = h[i] ;
        for(int j = 1 ; j <= lg[n] ; j ++)
            for(int i = 1 ; i + (1 << j) - 1 <= n ; i ++)
                st[i][j] = min(st[i][j - 1] , st[i + (1 << (j - 1))][j - 1]) ;
    }
    inline int LCP(int l , int r) {
        if(l > r) swap(l , r) ; ++ l ;
        int j = lg[r - l + 1] ;
        return min(st[l][j] , st[r - (1 << j) + 1][j]) ;
    }
}

namespace F_Tree {
    # define ls t[now].l
    # define rs t[now].r
    int tot , rt[M] ;
    void Insert(int x , int l , int r , int &now) {
        t[++tot] = t[now] ; now = tot ; t[now].sum ++ ;
        int mid = (l + r) >> 1 ;
        if(l == r) return ;
        if(mid >= x) Insert(x , l , mid , ls) ;
        else Insert(x , mid + 1 , r , rs) ;
    }
    void queryPre(int i , int j , int l , int r , int k , int now) {
        if(l == r) {
            if(t[j].sum > t[i].sum)
                ret = l ;
            return ;
        }
        int mid = (l + r) >> 1 ;
        if(!ret && mid < k) {
            if(!ret && t[t[j].r].sum - t[t[i].r].sum > 0) queryPre(t[i].r , t[j].r , mid + 1 , r , k , rs) ;
            if(!ret && t[t[j].l].sum - t[t[i].l].sum > 0) queryPre(t[i].l , t[j].l , l , mid , k , ls) ;
        }
        else if(!ret && mid >= k && t[t[j].l].sum - t[t[i].l].sum > 0) queryPre(t[i].l , t[j].l , l , mid , k , ls) ;
    }
    void queryNxt(int i , int j , int l , int r , int k , int now) {
        if(l == r) {
            if(t[j].sum > t[i].sum)
                ret = l ;
            return ;
        }
        int mid = (l + r) >> 1 ;
        if(!ret && mid > k) {
            if(!ret && t[t[j].l].sum - t[t[i].l].sum > 0) queryNxt(t[i].l , t[j].l , l , mid , k , ls) ;
            if(!ret && t[t[j].r].sum - t[t[i].r].sum > 0) queryNxt(t[i].r , t[j].r , mid + 1 , r , k , rs) ;
        }
        else if(!ret && mid <= k && t[t[j].r].sum - t[t[i].r].sum > 0) queryNxt(t[i].r , t[j].r , mid + 1 , r , k , rs) ;
    }
}

using namespace SA ;
using namespace F_Tree ;

inline LL Solve(int p) {
    LL Ans = 0 ; int lent ; 
    for(int i = 1 , temp ; i <= q[p].len ; i ++) {
        ret = 0 ; temp = 0 ;
//  先查在原序列里面的		
        queryPre(rt[q[p].l - 1] , rt[q[p].r] , 1 , n , rnk[q[p].stp + i] , rt[q[p].r]) ;
        if(ret) {
                lent = LCP(ret , rnk[q[p].stp + i]) ;
                if(lent && i + lent - 1 > q[p].len)
                    lent = q[p].len - i + 1 ;
                temp = max(temp , lent) ;
            }
        ret = 0 ;
        queryNxt(rt[q[p].l - 1] , rt[q[p].r] , 1 , n , rnk[q[p].stp + i] , rt[q[p].r]) ;
        if(ret) {
                lent = LCP(ret , rnk[q[p].stp + i]) ;
                if(lent && i + lent - 1 > q[p].len)
                    lent = q[p].len - i + 1 ;
                temp = max(temp , lent) ;
            }
        if(i > 1) {
            ret = 0 ;
            queryPre(rt[Fn] , rt[Fn + i - 1] , 1 , n , rnk[q[p].stp + i] , rt[Fn + i - 1]) ;
            if(ret) {
                lent = LCP(ret , rnk[q[p].stp + i]) ;
                if(lent && i + lent - 1 > q[p].len)
                    lent = q[p].len - i + 1 ;
                temp = max(temp , lent) ;
            }
            ret = 0 ;
            queryNxt(rt[Fn] , rt[Fn + i - 1] , 1 , n , rnk[q[p].stp + i] , rt[Fn + i - 1]) ;
            if(ret) {
                lent = LCP(ret , rnk[q[p].stp + i]) ;
                if(lent && i + lent - 1 > q[p].len)
                    lent = q[p].len - i + 1 ;
                temp = max(temp , lent) ;
            }
        }
        Ans += q[p].len - i + 1 - temp ;
        rt[Fn + i] = rt[Fn + i - 1] ;
        Insert(rnk[q[p].stp + i] , 1 , n , rt[Fn + i]) ;
    }
    return Ans ;
}
int main() {
    scanf("%s",tmp + 1) ; 
    Fn = strlen(tmp + 1) ; n = Fn ;
    for(int i = 1 ; i <= Fn ; i ++) s[i] = tmp[i] ;
    qnum = read() ;
    for(int i = 1 ; i <= qnum ; i ++) {
        scanf("%s",tmp + 1) ;
        q[i].len = strlen(tmp + 1) ;
        q[i].l = read() ; q[i].r = read() ; 
        s[++n] = 200 + i ;
        q[i].stp = n ;
        for(int j = 1 ; j <= q[i].len ; j ++) 
            s[++n] = tmp[j] ;
    }
    Make_SA() ;
    Build() ;
    for(int i = 1 ; i <= Fn ; i ++) {
        rt[i] = rt[i - 1] ;
        Insert(rnk[i] , 1 , n , rt[i]) ;
    }
    for(int i = 1 ; i <= qnum ; i ++) 
        printf("%lld\n",Solve(i)) ;
    return 0 ;
}

评测结果