HDU6704

发表于 | 阅读数

给定字符$S$,$q$个询问，询问$str[l..r]$,这个子串第$k$次出现的位置,不存在输出$-1$。($Strlen(S),q,k\leq 10^5$)

对于重复字串问题，选择后缀数组。对于与$suf(l),lcp$长度$\leq r-l+1$,一定出现在排好名的后缀数组里的某个区间。即寻找$i\in[下界，上界],sa[i]$排名在区间第$k$位。离散化下即可。

注意

  • 上下界二分即可找到
  • 计算$lcp(x,y)$,不需要像之前模版取$sa[x],sa[y]$,直接计算即可。
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
struct node
{
    int l, r, sum;
} tree[N << 5];
int tcnt;
int build(int l, int r)
{
    int pos = ++tcnt;
    if (l == r)
        return pos;
    int mid = (l + r) >> 1;
    tree[pos].l = build(l, mid);
    tree[pos].r = build(mid + 1, r);
    return pos;
}

int update(int pre, int l, int r, int x)
{
    int pos = ++tcnt;
    tree[pos].l = tree[pre].l;
    tree[pos].r = tree[pre].r;
    tree[pos].sum = tree[pre].sum + 1;
    if (l == r)
        return pos;
    int mid = (l + r) >> 1;
    if (x <= mid)
        tree[pos].l = update(tree[pre].l, l, mid, x);
    else
        tree[pos].r = update(tree[pre].r, mid + 1, r, x);
    return pos;
}
int query(int u, int v, int l, int r, int k)
{
    if (l == r)
        return l;
    int p = tree[tree[v].l].sum - tree[tree[u].l].sum;
    int mid = (l + r) >> 1;
    if (p >= k)
        return query(tree[u].l, tree[v].l, l, mid, k);
    else
        return query(tree[u].r, tree[v].r, mid + 1, r, k - p);
}

int sa[N], ra[N], y[N], tn[N], he[N];
int rq[N][20];
void get_SA(char *s, int len, int size)
{
    int tmp[N]; //辅助数组
    for (int i = 1; i <= size; i++)
        tn[i] = 0;
    for (int i = 1; i <= len; i++)
        ra[i] = s[i], tn[ra[i]]++;
    for (int i = 1; i <= size; i++)
        tn[i] += tn[i - 1];
    for (int i = len; i >= 1; i--)
        sa[tn[ra[i]]--] = i;
    for (int k = 1; k <= len; k <<= 1)
    {
        int cnt = 0;
        for (int i = len - k + 1; i <= len; i++)
            y[++cnt] = i;
        for (int i = 1; i <= len; i++)
            if (sa[i] > k)
                y[++cnt] = sa[i] - k;

        for (int i = 1; i <= size; i++)
            tn[i] = 0;
        for (int i = 1; i <= len; i++)
            tn[ra[i]]++;
        for (int i = 1; i <= size; i++)
            tn[i] += tn[i - 1];
        for (int i = len; i >= 1; i--) //倒叙原因是因为tn[ra[y[i]]]是桶里面最大的
            sa[tn[ra[y[i]]]--] = y[i];
        for (int i = 1; i <= len; i++)
            tmp[i] = ra[i];

        cnt = 1;
        ra[sa[1]] = 1;
        for (int i = 2; i <= len; i++)
            ra[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] == tmp[sa[i - 1] + k]) ? cnt : ++cnt;
        if (cnt == len)
            break;
        size = cnt;
    }

    int k = 0;
    for (int i = 1; i <= len; i++)
        ra[sa[i]] = i;
    for (int i = 1; i <= len; i++)
    {
        if (k)
            k--;
        int j = sa[ra[i] - 1];
        while (i + k <= len && j + k <= len && s[j + k] == s[i + k])
            k++;
        he[ra[i]] = k;
    }
    for (int i = 1; i <= len; i++)
        rq[i][0] = he[i];
    for (int i = 1; (1 << i) <= len; i++)
        for (int j = 1; j + (1 << i) - 1 <= len; j++)
            rq[j][i] = min(rq[j][i - 1], rq[j + (1 << (i - 1))][i - 1]);
}
int len;
int lcp(int x, int y)
{
    if (x == y)
        return len - sa[x] + 1;
    //x = ra[x], y = ra[y];
    if (x > y)
        swap(x, y);
    x++;
    int p = int(log(y - x + 1.0) * 1.0 / (1.0 * log(2)));
    return min(rq[x][p], rq[y - (1 << p) + 1][p]);
}
int T, m, tr[N];
char s[N];
int findl(int x, int p)
{

    int l = 1, r = x, ans = x;
    while (l <= r)
    {

        int mid = (l + r) >> 1;
        //cout << l << " " << r << " " << lcp(mid, x) << endl;
        if (lcp(mid, x) >= p)
        {
            r = mid - 1;
            ans = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}
int findr(int x, int p)
{
    int l = x, r = len, ans = x;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (lcp(mid, x) >= p)
        {
            l = mid + 1;
            ans = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    return ans;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &len, &m);
        scanf("%s", s + 1);

        tcnt = 0;
        len = strlen(s + 1);
        get_SA(s, len, 150);
        tr[0] = build(1, len);
        for (int i = 1; i <= len; i++)
            tr[i] = update(tr[i - 1], 1, len, sa[i]);
        for (int i = 1; i <= m; i++)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            int ll = findl(ra[l], r - l + 1);
            int rr = findr(ra[l], r - l + 1);
            //cout << lcp(2, 3) << endl;
            //cout << ll << " " << rr << endl;
            if (rr - ll + 1 < k)
                printf("-1\n");
            else
                printf("%d\n", query(tr[ll - 1], tr[rr], 1, len, k));
        }
    }
}