原题链接
这题珂以后缀数组。
先把所有串连起来，中间用$分隔，组成一个新字符串(S)。设(s_i)在(S)内的位置是(operatorname{st}_ildots operatorname{st}_i+operatorname{len}_i-1)。对(S)建后缀数组。
我们先求出在(S)的哪些后缀的前缀会出现(s_k)。在(operatorname{rank})上根据(operatorname{height})上二分出最左端点(l)和最右端点(r)使得(minlimits_{l<ile r}operatorname{height}_igeoperatorname{len}_k)。那么集合({j|j=operatorname{sa}_i,iin[l,r]})就是符合要求的所有下标所在的集合。设(L_k=l,R_k=r)。
我们现在要求的是(s_{[lldots r]})内的字符串共出现了多少次(s_k)，本质上是求符合(iin[operatorname{st}_l,operatorname{st}_r+operatorname{len}_r],operatorname{rank}_iin[L_k,R_k])条件的(i)的个数。这实际上是一个二维数点的问题。所以问题就做完了。
有一个要注意的是数组不能开小。还有一个是如果你用这种方法且二维数点sort时用的是C中的qsort，你会TLE(这也是为什么我这题不得不放弃C语言来交这题了)。
代码就放一下之前写的C版本的Time Limit Exceed on Test 18的吧(主要是后来那个加了1000多行的基数排序太长了)。
// Code by H~$~C
#pragma GCC optimize("Ofast,-funroll-loops")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <stdbool.h>
#include <time.h>
#define lambda(return_type, function_body)
({
return_type $this function_body
$this;
})
#define $ lambda // it won't allow comma (that is ',') without brackets in the function body!
#define inline __attribute__((__always_inline__)) __inline
#define eprintf(...) (fprintf(stderr, __VA_ARGS__) & fflush(stderr))
#define _InputSize (50 << 20)
#define _OutputSize (20 << 20)
static char _in_buf[_InputSize], _out_buf[_OutputSize];
char *_in_p = _in_buf, *_out_p = _out_buf;
__attribute__((constructor))
void read_buffer() { fread(_in_buf, 1, _InputSize, stdin); }
__attribute__((destructor))
void write_buffer() { fwrite(_out_buf, 1, _out_p - _out_buf, stdout); }
__attribute__((__always_inline__)) __inline
void read(int *n) {
while (*_in_p < 48 || *_in_p > 57) _in_p++;
for (*n = *_in_p++ ^ 48; *_in_p > 47 && *_in_p < 58; )
*n = (*n << 3) + (*n << 1) + (*_in_p++ ^ 48);
}
__attribute__((__always_inline__)) __inline
int readstr(char *str) {
while (*_in_p < 33) _in_p++;
register int len = 0;
while (*_in_p > 32) *str++ = *_in_p++, len++;
return len;
}
__attribute__((__always_inline__)) __inline
void write_char(char c) { *_out_p++ = c; }
__attribute__((__always_inline__)) __inline
void write(int n) {
static char _buf[10]; char* _pos = _buf;
do *_pos++ = n % 10 ^ 48; while (n /= 10);
while (_pos != _buf) *_out_p++ = *--_pos;
}
#define Maxn 400005
#define Maxm 500005
#define LOG 21
int n, m, q;
int st[Maxn], len[Maxn];
int L[Maxn], R[Maxn];
char s[Maxn];
int sa[Maxn], rnk[Maxn], height[Maxn];
int wa[Maxn], wb[Maxn], wc[Maxn], _s[Maxn];
void build_SA(char *ss, int n, int m) {
register int *x = wa, *y = wb, *tmp;
register int i, j, w;
for (i = 1; i <= n; ++i) _s[i] = ss[i];
for (i = 1; i <= n; ++i) x[i] = _s[i], y[i] = i;
for (i = 1; i <= m; ++i) wc[i] = 0;
for (i = 1; i <= n; ++i) wc[x[i]]++;
for (i = 2; i <= m; ++i) wc[i] += wc[i - 1];
for (i = n; i >= 1; --i) sa[wc[x[y[i]]]--] = y[i];
for (w = 1; w <= n; w <<= 1) {
register int tot = 0;
for (i = n - w + 1; i <= n; ++i) y[++tot] = i;
for (i = 1; i <= n; ++i) if (sa[i] > w) y[++tot] = sa[i] - w;
for (i = 1; i <= m; ++i) wc[i] = 0;
for (i = 1; i <= n; ++i) wc[x[i]]++;
for (i = 2; i <= m; ++i) wc[i] += wc[i - 1];
for (i = n; i >= 1; --i) sa[wc[x[y[i]]]--] = y[i];
tmp = x, x = y, y = tmp, x[sa[1]] = 1, tot = 1;
for (i = 2; i <= n; ++i)
x[sa[i]] = ((y[sa[i]] == y[sa[i - 1]] && y[sa[i] + w] == y[sa[i - 1] + w]) ? tot : ++tot);
if (tot == n) break; m = tot;
}
for (i = 1; i <= n; ++i) rnk[sa[i]] = i;
for (i = 1, w = 0; i <= n; ++i) {
if (rnk[i] == 1) continue;
if (w) --w;
int j = sa[rnk[i] - 1];
while (i + w <= n && j + w <= n && _s[i + w] == _s[j + w]) w++;
height[rnk[i]] = w;
}
}
// sa[rank] = name, rnk[name] = rank
// height[i] = lcp(suffix(sa[i - 1]), suffix(sa[i]))
int ST[LOG][Maxn];
int ans[Maxm];
#define C_Maxn (Maxn + Maxm * 4)
struct Query {
int op, id, x, y, val;
} qry[C_Maxn];
int tot;
void add_point(int x, int y) {
qry[tot++] = (struct Query){1, 0, x, y, 0};
}
void add_rectangle(int xl, int xr, int yl, int yr, int id) {
qry[tot++] = (struct Query){2, id, xl - 1, yl - 1, 1};
qry[tot++] = (struct Query){2, id, xl - 1, yr, -1};
qry[tot++] = (struct Query){2, id, xr, yl - 1, -1};
qry[tot++] = (struct Query){2, id, xr, yr, 1};
}
int compare_query(const struct Query *X, const struct Query *Y) {
struct Query x = *X, y = *Y;
if (x.x != y.x) return x.x - y.x;
return x.op - y.op;
}
int bit[Maxn];
int main() {
register int i, j;
read(&n), read(&q);
m = 0;
for (i = 1; i <= n; ++i) {
len[i] = readstr(s + (st[i] = m + 1));
s[st[i] + len[i]] = '$';
m = st[i] + len[i];
}
// eprintf("str = %s
", s + 1);
build_SA(s, m, 128);
// for (int i = 1; i <= m; ++i) eprintf("rnk[%2d] = %2d, sa[%2d] = %2d, height[%2d] = %2d
", i, rnk[i], i, sa[i], i, height[i]);
for (i = 1; i <= m; ++i) ST[0][i] = height[i];
for (j = 1; j < LOG; ++j)
for (i = 1; i + (1 << j) - 1 <= m; ++i) {
int a = ST[j - 1][i], b = ST[j - 1][i + (1 << (j - 1))];
ST[j][i] = (a < b ? a : b);
}
for (i = 1, j; i <= n; ++i) {
int l = rnk[st[i]], r = rnk[st[i]];
int length = len[i];
/* get the leftest position */ {
for (j = 0; l - (1 << j) + 1 >= 2; ++j);
for (; ~--j; ) {
if (l - (1 << j) + 1 >= 2 && ST[j][l - (1 << j) + 1] >= length) {
l -= (1 << j);
}
}
}
/* get the rightest position */ {
for (j = 0; r + (1 << j) <= m; ++j);
for (; ~--j; ) {
if (r + (1 << j) <= m && ST[j][r + 1] >= length) {
r += (1 << j);
}
}
}
L[i] = l, R[i] = r;
// eprintf("L[%d] = %d, R[%d] = %d
", i, L[i], i, R[i]);
}
tot = 0;
for (i = 1; i <= m; ++i) {
add_point(i, rnk[i]);
// fprintf(stderr, "(%d, %d)
", i, rnk[i]);
}
for (i = 1; i <= q; ++i) {
int l, r, k;
read(&l), read(&r), read(&k);
add_rectangle(st[l], st[r] + len[r], L[k], R[k], i);
}
qsort(qry, tot, sizeof *qry, compare_query);
for (i = 0; i < tot; ++i) {
// eprintf("qry[%d] = {%d, %d, %d, %d, %d}
", i, qry[i].op, qry[i].id, qry[i].x, qry[i].y, qry[i].val);
int x = qry[i].y;
if (qry[i].op == 1) {
while (x < Maxn)
bit[x]++, x += x & -x;
}
else {
int res = 0;
while (x) {
res += bit[x];
x -= x & -x;
}
ans[qry[i].id] += qry[i].val * res;
}
}
for (int i = 1; i <= q; ++i)
printf("%d
", ans[i]);
return 0;
}