k-string

给一个长度为n的字符串S,定义k-string为在字符串S中出现次数大于等于k次的子串,也就是存在至少k对(i,j)使得0 <= i <= j < n且Si,Si+1…Sj构成的子串与该k-string相同。现给一个初始字符串,然后执行m个操作,每个操作有两种:1.往当前字符串S末尾添加一个字符; 2.询问当前不同的k-string有多少种。

这题可以用sa的h数组做 也可以用构后缀树做
先说下sa的(我没写 只是随便写个思路=-=
【sa】
先把字符串倒过来 这样每次插入就等于插入一个后缀
给每个后缀一个编号 代表插入时询问到第几个询问了
h数组可以画成像这样的柱状图(左)
1
然后可以把它从上到下划分成好几个矩形(右)
划分可以排序+链表做

然后对于一个矩形 记录3个信息 l r h
对于这个矩形的贡献就是:l~r这些后缀中 第k个出现的时间
在这个时间后的询问 这个矩形都能对其贡献h的答案
可以维护一个数组记录改变量 最后扫一遍就可以了

询问k大 题解上写的是用划分树 主席树应该也可以

【后缀树】
其实sam构的是前缀树 那刚好连字符串都不用倒过来了
同样一个插入代表是多了一个前缀
用上面同样的方法对前缀进行标号
考虑parent树上一个节点的贡献
一个节点能有贡献 当且仅当它出现了k次 即它有k个出现了的叶子
而他的贡献是t[now].l – t[t[now].f].l
同样维护一个改变量数组即可
这里的k大是在一个类似dfs序上询问的

有一个值得注意的地方 这题的空间限制是64(32)M
直接用sam+主席树会MLE
有两种办法 1是把sam的ch数组改成map
我试了试 TLE了=-=

还有就是 从下往上计算 对每个节点维护一个大根左偏树
对于一个儿子都计算过的节点 把所有儿子合并
然后不停删根 直到树的大小为k 这时根就是第k小的时间点

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 100005;

struct node
{
    int ch[27], l, f;
}t[maxn * 2];

struct line
{
    int to, next;
}li[maxn * 4];

struct t_node
{
    int l, r, dis, v;
}tt[maxn];

int ans[maxn], is[maxn], tot, last, n, m, k, p, be[maxn * 2], l, tot_node, b[maxn * 2];
string s;

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

void add(char c, int len)
{
    c -= 'a';
    int now = ++tot, p = last;
    last = now;
    t[now].l = len;
    for (; p && !t[p].ch[c]; p = t[p].f) t[p].ch[c] = now;
    if (!p) t[now].f = 1;
    else
    if (t[p].l + 1 == t[t[p].ch[c]].l) t[now].f = t[p].ch[c];
    else
    {
        int r = ++tot, ch = t[p].ch[c];
        t[r] = t[ch];
        t[r].l = t[p].l + 1;
        t[ch].f = t[now].f = r;
        for (; p && t[p].ch[c] == ch; p = t[p].f) t[p].ch[c] = r;
    }
}

int merge(int a, int b)
{
    if (!a) return b;
    if (!b) return a;
    if (tt[a].v < tt[b].v) swap(a, b);
    tt[a].r = merge(tt[a].r, b);
    if (tt[tt[a].l].dis < tt[tt[a].r].dis) swap(tt[a].l, tt[a].r);
    tt[a].dis = tt[tt[a].r].dis + 1;
    return a;
}

pair<int, int> dfs(int now)
{
    int root = 0, sum = 0;
    if (!b[now] && t[now].l != 1)
    {
        ++tot_node;
        tt[tot_node].l = tt[tot_node].r = 0;
        tt[tot_node].dis = 1;
        tt[tot_node].v = is[t[now].l - 1];
        root = tot_node;
        sum = 1;
    }
    for (int i = be[now]; i; i = li[i].next)
    {
        pair<int, int> t = dfs(li[i].to);
        root = merge(root, t.first);
        sum += t.second;
    }
    if (now == 1 || sum < k) return make_pair(root, sum);
    while (sum > k) root = merge(tt[root].l, tt[root].r), --sum;
    ans[tt[root].v] += t[now].l - t[t[now].f].l - (!b[now] ? 1 : 0);
    return make_pair(root, sum);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    cin >> s;
    s = '{' + s;
    tot = last = 1;
    for (int i = 0; i < s.length(); ++i)
        add(s[i], i + 1), is[i] = 0;
    for (int i = 0; i < m; ++i)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            char tc, c;
            scanf("%c%c", &tc, &c);
            is[s.length()] = p;
            s += c;
            add(c, s.length());
        }
        else ++p;
    }
    for (int i = 1; i <= tot; ++i)
        makeline(t[i].f, i), b[t[i].f] = 1;
    tot_node = 1;
    dfs(1);
    int as = 0;
    for (int i = 0; i < p; ++i)
    {
        as += ans[i];
        printf("%d\n", as);
    }
    fclose(stdin);fclose(stdout);
}

发表评论