loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long 
#define ull unsigned long long 
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 4e5 + 10, INF = 1e9 + 1, mod = 1e9 + 7;
const double eps = 1e-9, pi = acos(-1);
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, Q, K;
char s[MAXN], w[MAXN];
string q[MAXN];
int l[MAXN], r[MAXN], a[MAXN], b[MAXN], pos[MAXN];
vector<int> line[1001][1001], v[MAXN];
int ch[MAXN][26], siz[MAXN], len[MAXN], fa[MAXN], las = 1, root = 1, tot = 1;
void insert(int x, int opt) {
    int now = ++tot, pre = las; las = now; len[now] = len[pre] + 1; siz[now] = opt; 
    for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;
    if(!pre) fa[now] = root; 
    else {
        int q = ch[pre][x];
        if(len[pre] + 1 == len[q]) fa[now] = q;
        else {
            int nq = ++tot; len[nq] = len[pre] + 1; fa[nq] = fa[q];
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            fa[now] = fa[q] = nq;
            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq;
        }
    }
}
void dfs(int x) {
    for(auto &to : v[x]) {
        dfs(to);
        siz[x] += siz[to];
    }
}
int Query(vector<int> &q, int a, int b) {
    return (upper_bound(q.begin(), q.end(), b) - lower_bound(q.begin(), q.end(), a));
}
LL solve1(int a, int b) {
    LL ret = 0;
    for(int i = 1; i <= K; i++) {
        int now = root;
        for(int j = i; j <= K; j++) {
            int x = w[j] - 'a'; now = ch[now][x];
            if(!now) break;
            else ret += 1ll * siz[now] * Query(line[i][j], a, b);
        }
    }
    return ret;
}
void Build() {
    for(int i = 1; i <= tot; i++) v[fa[i]].push_back(i);
    dfs(root);
}
signed main() {
//  freopen("string9.in", "r", stdin);  freopen("b.out", "w", stdout);
    N = read(); M = read(); Q = read(); K = read(); 
    scanf("%s", s + 1);
    for(int i = 1; i <= N; i++) insert(s[i] - 'a', 1);
    if(K <= 1000) {
        Build();
        for(int i = 1; i <= M; i++) l[i] = read() + 1, r[i] = read() + 1, line[l[i]][r[i]].push_back(i);
        for(int i = 1; i <= Q; i++) {
            scanf("%s", w + 1); int a = read() + 1, b = read() + 1;
            cout <<  solve1(a, b) << '\n';
        }
    } 
    else {
        for(int i = 1; i <= M; i++) l[i] = read() + 1, r[i] = read() + 1;
        for(int i = 1; i <= Q; i++) {
            cin >> q[i]; a[i] = read() + 1, b[i] = read() + 1;
            las = 1;
            for(auto &x : q[i]) insert(x - 'a', 0);
        }
        Build();
        for(int i = 1; i <= Q; i++) {
            memset(pos, 0, sizeof(pos));
            int now = root;
            for(int j = 0; j < q[i].length(); j++) {
                int x = q[i][j] - 'a'; now = ch[now][x];
                if(!now) break;
                else pos[j + 1] = now;
            }
            LL ans = 0;
            for(int j = a[i]; j <= b[i]; j++) {
                int cur = pos[r[j]];
                while(len[fa[cur]] >= r[j] - l[j] + 1) cur = fa[cur];//这里可以卡掉
                ans += siz[cur];
            }
            cout << ans << '\n';
        }
    }
    return 0;
}