题面

求模板串 $S$ 在 $T$ 中的出现次数。

其中 $1 \le |S|, |T| \le 10^7$.

时间限制 $5$ 秒, 内存限制 $\mathbf{1}$ MB, 且输入只能读取一次.

题解

KMP 模板题

题目让你在一个空间受限的背景下, 进行流式字符串匹配. 本题无论模板串还是询问串都无法放进内存, 你必须流式的一个一个读取.

首先, 回忆 Rabin-Karp 算法是怎么样的. 它对模板串 $S$ 求了一个 hash 值, 然后使用滑动窗口 维护询问串所有长度 $S$ 的子串的 hash 值, 这里时间复杂度是 $O(|T|)$ 的, 但是空间复杂度是 $O(|S|)$ 的 (需要存下整个窗口, 以供删除开头的字符). 显然无法满足本题的要求.

官方题解的做法:

1. 读入模板串 $S$, 计算出长度为 $\lfloor \sqrt{n} \rfloor$ 的前缀 hash 值和完整串的 hash 值, 时间复杂度 $O(|S|)$, 空间复杂度 $O(1)$;
2. 读入询问串 $T$, 维护 $\lfloor \sqrt{n} \rfloor$ 大小的滑动窗口, 可以求出询问串中所有和这个根号前缀匹配的位置. 相当于, 筛出去了一些必不可能匹配上的位置, 留下来一些位置需要求出相应的全长度的 hash 值.
   • 注意到, 直到这里实际上还没有本质的改善, 一是匹配上的位置仍然很多, 二是难以搞出相应的全串 hash 值.
   • 根据 (Weak) Periodicity Lemm, 我们可以把匹配上的位置分成至多 $\lceil \sqrt{n} \rceil$ 组等差数列. 具体的, 每组中所有匹配的子串是一个顺次有重叠的列表, 相邻出现位置的距离差相等 (也就是所谓的构成等差数列, 进一步, 重叠部分其实就是根号前缀的 border). 于是, 记录匹配位置的空间被压缩到了 $O(\lfloor \sqrt{n} \rfloor)$.
   • 下一个问题是, 我们不仅需要记录匹配的位置, 还需要记录匹配处的前缀 hash 值, 等到处理到该次可能匹配的结束位置时来进行全串的比对. 同样根据上述引理的结论, 同一组等差数列内部, 相邻 2 个匹配位置之间的 hash 值是固定的, 我们只需要记录等差数列的起点, 公差, 终点, 起点的 hash 值, 公差对应字符串部分的 hash 值, 就能表示出这一个等差数列的所有位置信息和 hash 值信息.

最终, 时间复杂度 $O(n)$, 空间复杂度 $O(\lfloor \sqrt{n} \rfloor)$, 一是维护滑动窗口, 二是维护所有等差数列.

周期相关理论的参考文献:

• 金策, 《字符串算法选讲》
• 2019 年集训队论文, 陈孙立, 《子串周期查询问题的相关算法及其应用》

官方题解

分块 KMP

一个不要 period 的做法, 大概是把模式串分成 sqrt 个字符一块, 每块合并成一个大字符，然后关于大字符跑 sqrt 个并排的 kmp

代码

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
198
199
200

#include <cmath>
#include <cstdio>
#include <random>
#include <vector>

using namespace std;

const int base = 131;
const int SZ = 3162;
const int cap = 4096;

namespace {
  // biv = base^{-1}, bsziv = base^{-SZ+1}
  int mod, biv, bsizv;

  random_device rd;
  mt19937 rnd(rd());
  uniform_int_distribution<> gen(100000000, 900000000);

  bool isPrime(int n) {
    if (n % 2 == 0) return false;
    int sq = (int) sqrt(n) + 1;
    for (int i = 3; i <= sq; i += 2) {
      if (n % i == 0) return false;
    }
    return true;
  }

  int add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
  }

  int sub(int a, int b) {
    a -= b;
    if (a < 0) a += mod;
    return a;
  }

  int mul(int a, int b) {
    return 1ll * a * b % mod;
  }

  int qpow(int x, int n) {
    int r = 1;
    while (n) {
      if (n & 1) r = mul(r, x);
      n >>= 1;
      x = mul(x, x);
    }
    return r;
  }

  void init() {
    while (true) {
      mod = gen(rnd);
      if (isPrime(mod)) {
        break;
      }
    }
    biv = qpow(base, mod - 2);
    bsizv = qpow(qpow(base, SZ - 1), mod - 2);
  }
}

int n, m, preh = 0, allh = 0;

struct Ring {
  char buf[cap];
  int head = 0, tail = 0, size = 0, len;
  int hsh = 0, xp = 1;

  void init(int n) {
    len = n;
    hsh = 0;
    head = tail = size = 0;
    xp = 1;
  }

  char pop() {
    size--;
    char x = buf[(head++) % cap];
    return x;
  }

  void push(char x) {
    size++;
    buf[(tail++) % cap] = x;
  }

  void append(char c) {
    push(c);
    hsh = add(mul(c, xp), hsh);
    if (size > len) {
      hsh = sub(hsh, pop());
      hsh = mul(hsh, biv);
    } else {
      xp = mul(xp, base);
    }
  }
} f;

struct Per {
  int start, delta = -1, end = -1;
  int xp, hsh, dhsh = -1;

  Per(int p, int x, int h) : start(p + 1 - SZ) {
    end = start;
    xp = mul(x, bsizv);
    hsh = sub(h, mul(preh, xp));
  }

  bool next(int p, int curx, int curh) {
    p = p + 1 - SZ;
    if (delta == -1) {
      if (p - start >= SZ) {
        // it should have overlap part
        return false;
      } else {
        // set delta
        end = p;
        delta = end - start;
        curh = sub(curh, mul(preh, mul(curx, bsizv)));
        dhsh = sub(curh, hsh);
        return true;
      }
    } else {
      if (p - end == delta) {
        end = p;
        return true;
      } else {
        return false;
      }
    }
  }

  bool match(int pos, int curv) {
    if (start + n - 1 == pos) {
      int target = sub(curv, hsh);
      bool ok = target == mul(allh, xp);
      if (delta != -1) {
        start += delta;
        int dxp = qpow(base, delta);
        xp = mul(xp, dxp);
        hsh = add(hsh, dhsh);
        dhsh = mul(dhsh, dxp);
      }
      return ok;
    }
    return false;
  }
};

int main() {
  init();

  scanf("%d%d", &n, &m);
  getchar(); // end of line

  for (int i = 1, xp = 1; i <= n; i++, xp = mul(xp, base)) {
    char c = getchar();
    int val = mul(c, xp);
    if (i <= SZ) {
      preh = add(preh, val);
    }
    allh = add(allh, val);
  }
  getchar(); // end of line

  f.init(n <= SZ ? n : SZ);
  int ans = 0, curv = 0, matched = 0;
  vector<Per> ps;
  for (int i = 1, xp = 1; i <= m; i++, xp = mul(xp, base)) {
    char c = getchar();
    f.append(c);
    if (n <= SZ) {
      ans += f.size == n && f.hsh == allh;
    } else {
      curv = add(curv, mul(c, xp));
      if (f.size == SZ && f.hsh == preh) {
        // match the sqrt prefix
        // extend the last group or create a new group
        if (ps.empty() || !ps.back().next(i, xp, curv)) {
          ps.emplace_back(i, xp, curv);
        }
      }
      if (matched < ps.size()) {
        ans += ps[matched].match(i, curv);
        if (ps[matched].end + n - 1 == i) {
          matched++;
        }
      }
    }
  }

  printf("%d\n", ans);

  return 0;
}

题面

给定一个长度为 $5000$ 的正则表达式和一个长度为 $10000$ 的文本串，求文本串最少修改多少次能够被正则表达式识别。

题解

对正则表达式构造 NFA，令 $f(l,i)$ 表达式使用完前 $l$ 个字符后，到达了 NFA 的状态 $i$ 时的最小修改次数，转移方程的形式为求一个 $0/1$ 最短路。

XLex 正则表达式

2021 Shandong Provincial Collegiate Programming Contest

题面

榜单

题面

有一个长度为 $n$ 的未知数组，第 $i$ 个位置的值有有 $k_i$ 种选择，这个位置选择 $V(i,j)$ 的代价 $C(i,j)$。

当你确定数组后，有 $q$ 次询问 $[l, r]$ 区间内的最大值，这个数组的价值就是所有询问的和减去选数时的代价。

数据范围：$1 \le n \le 300, n \le \sum_{i=1}^n k_i \le 3 \cdot 10^5$。

分析

考虑区间 DP，令 $f(l, r)$ 表示确定完区间 $[l, r]$ 的价值。

预处理每个位置 $i$ 被区间 $[l, r]$ 内所有询问覆盖的次数。转移时可以枚举这个区间的某一个位置作为最大值，但是每一个位置有多种选择，这个位置不仅要在价值上比较优，还需要满足比上一层小的限制。

无视上面的区间 DP，我们对于一个点，可以发现这个点产生的贡献关于覆盖次数是一堆一次函数的 $\max$，也就是一个下凸壳。回到上面的 DP，我们在枚举最大值，使用预处理的覆盖次数，可以在凸壳上二分出对应的一次函数，得到最优价值。

其实，我们已经做完了，上面的算法已经能够得到最优解，且最优解一定是合法的。

简单证明一下，我们考虑点 $i$ 和点 $j$，假设点 $i$ 作为大区间时的被覆盖次数为 $x_1$，小区间 $x_2$，点 $j$ 类似地为 $x_3$ 和 $x_4$，显然 $x_1 > x_2, x_3 > x_4$。不妨设两个点 $i < j$ 分别只有两条线段 $f(x) = k_i x - b_i$ 和 $f(x) = k_j x - b_j$，且 $k_i > k_j$。因此，$i$ 必须作为大区间的最大值，而 $j$ 需要在内层。

合法解时的价值为 $k_i x_1 - b_i + k_j x_4 - b_j$，非法解时的价值为 $k_i x_2 - b_i + k_j x_3 - b_j$。

注意到 $x_1 - x_2 = x_3 - x_4$，因为这个差是所有区间左端点在 $i$ 左侧和右端点在 $j$ 右侧。

因此 $k_i (x_1 - x_2) > k_j (x_3 - x_4)$。

B Playlist

给定一个环形的数组 $a_1, a_2, \dots, a_n$，有一个指针 $p$ 在环上进行扫描，如果当前位置和上一个位置的数 $\gcd = 1$，那么删除当前位置，指针移到下一个位置重新开始，直到无法删除。

我们不能暴力模拟，因为每次可能会跳 $O(n)$ 次来找到目标删除的位置。例如：$2 \times 3, 3 \times 5, \dots, p$，每次会删除第一个数。

因此，我们需要优化这个找删除位置的过程。注意到，记 $\text{next}(i)$ 表示在剩下的位置中 $i$ 后面的那一个（环的意义下）。如果 $\gcd(a[i], a[\text{next}(i)]) > 1 $，那么这个 $i$ 位置和他后面的这一对数，在之后永远不会被当作一对删除，因此我们在找删除对的时候，不再需要考虑位置 $i$。因为，我们在不会跳过 $i$ 来删除 $i$ 后面那个，$i$ 后面那个会一直存在，直到 $i$ 被前面的删除，导致其变换前驱。

C Skyline Photo

给定一个排列 $h_1, h_2, \dots, h_n$，将这个数组划分为多个段，每个段的权值是 $h$ 的最小位置 $i$ 的权值 $b_i$，总权值是所有权值的和，求最大权值。

显然，如果权值都是正数那么只要分成长度为 $1$ 的段即可。考虑 $f(i)$ 表示以 $i$ 结尾的最大权值，那么这个权值会一直存活到下一个 $h$ 比它小的位置，这部分维护一个扫描线。然后考虑 $f(i)$ 是怎么得到的，会有两部分转移一部分是从上一个比它小的位置到这个位置的一段区间中取一个最大的，或者是从扫描线中取一个最大的。

D Useful Edges

给定一个带边权的无向图和 $q$ 组条件三元组 $(u,v,l)$。对于边 $(a,b)$，如果存在三元组 $(u,v,l)$ 和一条 $u \to v$ 的路径，满足这条路径权值和小于等于 $l$，并且 $(a,b)$ 在这条路径上，那么这条边是好边。求好边个数。

跑一下 Floyd 之后，对于一条权值为 $w$ 边 $(a,b)$，把条件列出来，存在 $1 \le i \le q$，满足 $dis(u_i,a)+w+dis(b,v_i) \le l_i$。注意到条件三元组会有 $O(n^2)$，显然不能全部枚举来判断。

移项 $w + dis(b,v_i) \le l_i - dis(u_i, a)$，这个式子的左边固定一个端点 $b$，我们枚举另外一个端点 $v_i$，然后希望预处理右边的最大值来直接判断。此时对于式子的右边就是对于固定的端点 $a$，在所有点 $1 \le u \le n$ 中，取最大的 $l(u,v) - dis(u, a)$。我们提取 $v$ 和 $a$ 作为键，$u$ 是唯一的变元，因此枚举 $u$ 预处理最大值，即可直接判断。

F Exam

给定 $n$ 个串，求有多对串 $(i,j)$ 满足 $s_i$ 是 $s_j$ 的子串，并且不存在 $k$ 使得 $s_i$ 是 $s_k$ 的子串，$s_k$ 是 $s_j$ 的子串。

首先，建出 AC 机，预处理每个点往上走第一个结束节点和 fail 树的 dfs 序。

我们枚举每一个串，计算它有多少个直接的子串。显然直接子串一定是，这个串所有前缀的最长后缀，满足这个后缀在字典中出现过，直接使用 AC 机预处理的信息容易得出（注意，完整串可能需要特判，因为完整串的最长后缀是其本身）。但是这些串中显然会有很多重复的，也会有很多串在另外的当中出现过。

我们结合 AC 机的结构，观察一下哪些串是重复的。显然每个最长后缀对应节点，在 fail 树上到根的路径都是出现过的，这些节点的串构成母串的所有子串。

但是，考虑下面这样的情况：

对于那个最长的绿串实际上被包含在蓝串内部，但是根据我们上述的做法，我们多统计了绿串。因为上述做法，只排除了后缀的情况，没有排除不是后缀而是内部的情况。

正确做法是，我们可以通过从右往左枚举右端点，记录单调下降的左端点，将所有左端点变化处作为询问的关键点，这样就能够排除串在内部的情况。

题面

给定一棵 $n$ 个点的树，每个点有权值 $a_i$ 和 $b_i$，定义 $f(x)$ 表示满足 $a_i$ 之和等于 $x$ 的所有树上独立集中，$b_i$ 权值和最大的方案数。你需要求出 $f(1), f(2), \dots, f(m)$ 的值。

其中 $1 \le n \le 50, 1 \le m \le 5000$。

分析

显然有一个 $f(i,j,0/1)$ 的 $O(nm^2)$ 的树形背包做法，无法通过。

我们考虑在 dfs 序上进行 DP，注意到一个点能否被选择只和它到根的链上的状态有关，于是我们按照 dfs 序枚举时，同时记录每种链上的状态的信息。但是，这样仍然难易通过，因为可能会存在一个长链。

对于树进行轻重链剖分，不同于传统的剖分后标号方式，我们首先标记轻子树的 dfs 序，然后标记重子树。对于这样的标号方式，当我们考虑 dfs 序上的第 $i$ 个转移到第 $i+1$ 个时，要么是沿着向下的边走了一步，要么是跳到该重链链头的父亲后，往下走了一步，或者重复往上跳链头的父亲，然后往下走一步。那么，以这样的方式标号后，每个点到根的路径上有用的点，就只有每条重链的底部节点（每条重链链头的父节点）。于是，我们对这些关键点进行状压。

转移时，需要考虑第 $i$ 个点上的关键点集合和第 $i+1$ 个点上的关键点集合的重复部分，得到具体的转移状态，分成使用节点 $i+1$ 和不使用节点 $i+1$ 两种进行转移。

2019 年 CCPC 秦皇岛 G Game on Chessboard

题面

给定一个 $12 \times 12$ 的正方形棋盘，放了黑白两种棋子，每个格子有权值 $w(i,j)$。有两种操作，删除一个棋子 $(i,j)$，花费为 $w(i,j)$，删除一对黑白棋子 $(i_1,j_1)$ 和 $(i_2,j_2)$，并且满足这两个棋子的左下角范围内不能有其它棋子，花费为 $|w(i_1,j_1)-w(i_2,j_2)|$。求删除所有棋子的最小花费。

分析

注意到，每次能够删除的棋子在一条从坐上到右下的轮廓线上，对轮廓线进行状压，$0$ 表示向下，$1$ 表示向右。

轮廓线有 $2n \choose n$ 条，状压枚举时，找到拐角点进行转移。

时间复杂度 $O(n^2 {2n \choose n})$。

2020 年 ICPC 上海 F Fountains

题面

给定一个长度为 $9$ 的序列 $a_1, a_2, \dots, a_n$，求选出 $k=1,2,\dots,\frac{n(n+1)}{2}$ 个不同的子区间时，最大化 $\sum_{L \le R} \max_{i=1}^k [L \le l_i \le r_i \le R] w(l_i, r_i)$，其中 $w(l,r)=\sum_{i=l}^r a_i$。

分析

首先，我们将线段 $[l,r]$ 看成平面上的一个点 $(l,r)$，显然这个点左上角的点对应线段都包含线段 $[l,r]$。

对所有子区间线段按权值由大到小排序，考虑 $dp(i,j,S)$ 表示考虑到了前 $i$ 条线段，选出了 $j$ 个，状态 $S$ 内的所有区间都已经确定了包含的线段，显然 $S$ 是一个从左下角到右上角的轮廓线。当我们枚举下一个放进来的线段时，就和原有状态求一个并，因为排序的缘故，只需要更新没有更新过的点的答案，同时维护出新的轮廓线。

时间复杂度 $O((\frac{n(n+1)}{2})^2 {2n \choose n})$。

题面

依次将 $n$ 个下边界在 $x$ 轴上的矩形涂黑，求每次涂色后总图形的周长。

其中 $1 \le n \le 2 \times 10^5$。

分析

横线部分就是线段覆盖，这是平凡的。

竖线部分，更新操作就是区间取 $\max$，对于线段树节点 $[l,r]$，需要维护 $\sum_{i=l}^{r-1} |a_{i}-a_{i+1}|$。

考虑 Segment Tree Beats，我们在线段树节点维护了区间最小值和区间次小值。当最大值更新为 $x$，$x$ 小于节点次大值，将区间内所有最小值提升为 $x$，可以发现这个过程中改变的是最小值和相邻高点之间的差。因此，我们对于一个线段树节点区间，维护所有相邻的是否是最小值导致间断点，假设我们维护了这样的间断点个数，那么对于区间答案的容易进行更新。

间断点的个数容易维护，首先它可能从左右子树上传得到，然后在考虑将左右区间拼接点的贡献即可。

最后，注意我们区间覆盖最小值时打的标记，也包含了懒标记效果，记得下传信息。注意维护次小值的细节。