代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAX_N 500007
#define MAX_T 1000007

char s[MAX_T];
int N, M;
int head[MAX_T], to[MAX_T], nxt[MAX_T], cap;
int lck, bg[MAX_T], ed[MAX_T];
int rt[MAX_T];
int tt[MAX_T * 20], ls[MAX_T * 20], rs[MAX_T * 20], siz;
int mx[MAX_T], pos[MAX_T];

inline void addEdge (int u, int v) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
}

void build (int l, int r, int& x, int y, int pos) {
    if (l > r || l > pos || r < pos) return;
    x = ++siz;
    tt[x] = tt[y] + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid) rs[x] = rs[y], build(l, mid, ls[x], ls[y], pos);
    if (mid < pos) ls[x] = ls[y], build(mid + 1, r, rs[x], rs[y], pos);
}

struct sam {
    int last, sz, root;
    bool has[MAX_T * 2];

    sam () {
	last = sz = root = 1;
    }

    struct node {
        int fa, mx;
        int go[30];
        node () {}
        node (int mx_) : fa(0), mx(mx_) {
            memset(go, 0, sizeof(go));
        }
    }t[MAX_T * 2];

    inline void init () {
        last = sz = root = 1;
        memset(t[root].go, 0, sizeof(t[root].go));
        t[root].fa = t[root].mx = 0;
	memset(has, false, sizeof(has));
    }

    inline void insert (int c, int idx) {
        int p = last, np = ++sz;
	has[np] = true, pos[np] = idx;
        t[np] = node(t[p].mx + 1);
        while (p && !t[p].go[c]) t[p].go[c] = np, p = t[p].fa;
        if (!p)
            t[np].fa = root;
        else {
            int q = t[p].go[c];
            if (q > MAX_T * 2 || p > MAX_T * 2) exit(1);
            if (t[q].mx == t[p].mx + 1)
                t[np].fa = q;
            else {
                int nq = ++sz;
                t[nq] = node(t[p].mx + 1);
		pos[nq] = pos[q];
                memcpy(t[nq].go, t[q].go, sizeof(t[nq].go));
                t[nq].fa = t[q].fa;
                t[q].fa = t[np].fa = nq;
                while (p && t[p].go[c] == q) t[p].go[c] = nq, p = t[p].fa;
            }
        }
        last = np;
    }

    void dfs (int x) {
        bg[x] = ++lck;
	pos[lck] = x;
	for (int i = head[x]; i; i = nxt[i])
	    dfs(to[i]);
        ed[x] = lck;
    }

    inline void bld () {
        for (int i = 2;i <= sz; ++i) addEdge(t[i].fa, i);
        dfs(root);
        for (int i = 1;i <= lck; ++i)
            if (has[pos[i]]) build(1, N, rt[i], rt[i - 1], t[pos[i]].mx);
            else rt[i] = rt[i - 1];
    }
}t1, t2;

int query (int l, int r, int x, int y, int totl, int totr) {
    if (l > r || l > totr || r < totl) return 0;
    if (totl <= l && r <= totr) return tt[x] - tt[y];
    int mid = l + r >> 1, ans = 0;
    if (totl <= mid) ans += query(l, mid, ls[x], ls[y], totl, totr);
    if (mid < totr) ans += query(mid + 1, r, rs[x], rs[y], totl, totr);
    return ans;
}

inline bool valid (int p, int l, int r) {
    if (!p) return false;
    return query(1, N, rt[ed[p]], rt[bg[p] - 1], l, r) > 0;
}

int main () {
    freopen ("name.in", "r", stdin);
    freopen ("name.out", "w", stdout);
    scanf("%s", s);
    N = strlen(s);
    for (int i = 0;i < N; ++i)
        t1.insert(s[i] - 'a', i);
    t1.bld();
    int Q, l, r;
    scanf("%d", &Q);
    while (Q--) {
        t2.init();
        scanf("%s%d%d", s, &l, &r);
        M = strlen(s);
        for (int i = 0;i < M; ++i) t2.insert(s[i] - 'a', i);
        int lon = 0, p = t1.root;
        for (int i = 0;i < M; ++i) {
	    //printf("%d %d %d %d %d\n", p, lon, l, r, l + lon);
	    while (1) {
	    	if (valid(t1.t[p].go[s[i] - 'a'], l + lon, r)) {
	    	    p = t1.t[p].go[s[i] - 'a'], lon++;
	    	    break;
	    	}
	    	if (lon == 0) break;
	    	lon--;
	    	if (lon == t1.t[t1.t[p].fa].mx) p = t1.t[p].fa;
	    }
	    mx[i] = lon;            
        }
	long long res = 0;
	for (int i = 2;i <= t2.sz; ++i) res += std::max(0, t2.t[i].mx - std::max(t2.t[t2.t[i].fa].mx, mx[pos[i]]));
        for (int i = 2;i <= t2.sz; ++i) mx[i] = 0;
	printf("%lld\n", res);
    }
    return 0;
}
/*
	    if (valid(t1.t[p].go[s[i] - 'a'], l + lon, r))
	        lon++, p = t1.t[p].go[s[i] - 'a'];
	    else {
	        while (p && !valid(t1.t[p].go[s[i] - 'a'], l + lon, r))
	            p = t1.t[p].fa;
	        if (!p)
	            lon = 0, p = t1.root;
	        else
	            lon = t1.t[p].mx + 1, p = t1.t[p].go[s[i] - 'a'];
	    }
	    mx[i] = lon;
*/

评测结果