Problem Description
You are given a string S consisting of only lowercase english letters and some queries.

For each query (l,r,k), please output the starting position of the k-th occurence of the substring SlSl+1...Sr in S.

Input
The first line contains an integer T(1≤T≤20), denoting the number of test cases.

The first line of each test case contains two integer N(1≤N≤105),Q(1≤Q≤105), denoting the length of S and the number of queries.

The second line of each test case contains a string S(|S|=N) consisting of only lowercase english letters.

Then Q lines follow, each line contains three integer l,r(1≤l≤r≤N) and k(1≤k≤N), denoting a query.

There are at most 5 testcases which N is greater than 103.

Output
For each query, output the starting position of the k-th occurence of the given substring.

If such position don't exists, output −1 instead.

题意：查找子串第k次出现的位置

题解：后缀数组 + 二分 + 倍增 + 主席树

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;
const int inf = 1e9;

struct SA {
    int dp[maxn][20], sa[maxn], rak[maxn];
    int tx[maxn], height[maxn], lg[maxn];
    int n, m, p;
    char s[maxn];
    struct node {
        int x, y, id;
    } a[maxn], b[maxn];

    void rsort() {
        for (int i = 1; i <= m; i++) tx[i] = 0;
        for (int i = 1; i <= n; i++) tx[a[i].y]++;
        for (int i = 1; i <= m; i++) tx[i] += tx[i - 1];
        for (int i = 1; i <= n; i++) b[tx[a[i].y]--] = a[i];
        for (int i = 1; i <= m; i++) tx[i] = 0;
        for (int i = 1; i <= n; i++) tx[b[i].x]++;
        for (int i = 1; i <= m; i++) tx[i] += tx[i - 1];
        for (int i = n; i >= 1; i--) a[tx[b[i].x]--] = b[i];
    }

    void ssort() {
        rsort();
        p = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) ++p;
            rak[a[i].id] = p;
        }
        for (int i = 1; i <= n; i++) {
            a[i].x = rak[i];
            a[i].id = sa[rak[i]] = i;
            a[i].y = 0;
        }
        m = p;
    }

    void solve() {
        m = maxn - 1;
        for (int i = 1; i <= m; i++) {
            a[i].x = a[i].y = s[i];a[i].id = i;
        }
        ssort();
        for (int j = 1; j <= n; j <<= 1) {
            for (int i = 1; i + j <= n; i++) a[i].y = a[i + j].x;
            ssort();
            if (p == n) break;
        }
        get_Height();
    }

    void get_Height() {
        int k = 0;
        for (int i = 1; i <= n; i++) {
            if (k) k--;
            int j = sa[rak[i] - 1];
            while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
            height[rak[i]] = k;
        }
        RMQ();
    }

    void RMQ() {
        for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i <= n; i++) dp[i][0] = height[i];
        for(int j = 1; j <= lg[n]; j++) {
            for(int i = 1; i + (1 << j) - 1 <= n; i++) {
                dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int lcp(int x, int y) {
        int l = rak[x], r = rak[y];
        if (l > r) swap(l, r);
        l++;
        int k = lg[r - l + 1];
        return min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }

    int check(int l, int r) {
        if (l == r) return dp[l][0];
        if (l > r) swap(l, r);
        int k = lg[r - l + 1];
        return min(dp[l][k], dp[r - (1 << k) + 1][k]);
    }
} sa;


struct Tree {
    int lson, rson;
    int sum;
} tree[maxn * 40];
int root[maxn], tot;

void insert(int &nowp, int last, int l, int r, int x) {
    nowp = ++tot;
    tree[nowp] = tree[last];
    tree[nowp].sum++;
    if (l == r) return;
    int mid = (l + r) / 2;
    if (mid >= x) {
        insert(tree[nowp].lson, tree[last].lson, l, mid, x);
    } else {
        insert(tree[nowp].rson, tree[last].rson, mid + 1, r, x);
    }
}

int query(int lt, int rt, int l, int r, int k) {
    if (l == r) {
        return l;
    }
    int lsum = tree[tree[lt].lson].sum;
    int rsum = tree[tree[rt].lson].sum;
    int mid = (l + r) / 2;
    if (rsum - lsum >= k) {
        return query(tree[lt].lson, tree[rt].lson, l, mid, k);
    } else {
        return query(tree[lt].rson, tree[rt].rson, mid + 1, r, k - rsum + lsum);
    }
}


int main() {
//    freopen("in.in", "r", stdin);
//    freopen("out1.out", "w", stdout);
    int T, m, l, r, k;
    scanf("%d", &T);
    while (T--) {
        tot = 0;
        memset(root, 0, sizeof(root));
        scanf("%d%d", &sa.n, &m);
        scanf("%s", sa.s + 1);
        sa.solve();
        for (int i = 1; i <= sa.n; i++) {
            insert(root[i], root[i - 1], 1, sa.n, sa.sa[i]);
        }
        while (m--) {
            int mm = inf;
            scanf("%d%d%d", &l, &r, &k);
            int L = sa.rak[l], R = sa.rak[l];
            int ll = sa.rak[l] + 1, rr = sa.n;
            int post = sa.rak[l] + 1;
            while (ll <= rr) {
                int mid = (ll + rr) / 2;
                if (sa.check(post, mid) >= r - l + 1) {
                    R = mid;
                    ll = mid + 1;
                } else {
                    rr = mid - 1;
                }
            }
            ll = 1, rr = sa.rak[l];
            post = sa.rak[l];
            while (ll <= rr) {
                int mid = (ll + rr) / 2;
                int x = sa.check(post, mid);
                if (x >= r - l + 1) {
                    L = mid - 1;
                    rr = mid - 1;
                } else {
                    ll = mid + 1;
                }
            }
            if (R - L + 1 < k) {
                printf("-1\n");
            } else {
                printf("%d\n", query(root[L - 1], root[R], 1, sa.n, k));
            }
        }

    }
    return 0;
}