这就是用来记录我对于《信息学奥赛一本通 · 提高篇》一书中的习题的刷题记录以及学习笔记。
一般分专题来写（全部写一起可能要加载很久...），比如本章就是用来记录KMP的。
再插一句：Loj 真是个不错的 OJ，如果说洛谷是最棒的 OIer 社区，那 Loj 就是最棒的刷题专区。
PS：这里的“最棒的”仅仅指带给我的练习感觉最好，例如画风好康，且仅代表个人意见。
专题介绍：KMP，快速单模匹配算法，反正很有用就对了。对于初学者来说，看似苦涩难懂，实则十分简单。
如果不会可以康康我的文章（自己去主页找），记住，有时并不需要全部的 KMP，而是其 \(next[]\) 的巧妙运用。
还有，仅仅会背模板是不够的，必须牢固掌握其原理才能做到做题时游刃有余。
KMP 模板题？不存在的。
如果你开开心心的交了一个 KMP 模板就会发现自己在样例 2 （aaaaaa aa）时就 GG 了。
因为这里的查询是删除式的，什么意思？就是找到一个就删除一个，所以样例 2 的答案为 3。
那怎么办？各种书上都没有讲啊（有原题的书籍除外）。
这里就要求你掌握 KMP 的本质啦。在计算答案时，一般的程序时酱紫的：
void kmp() {
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && (j == n || a[i] != b[j + 1])) j = nxt[j];
if (a[i] == b[j + 1])
++j;
if (j == m) ++ans;
}
return;
}
但是这肯定不行啊，那怎么办？看下面代码：
void kmp() {
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && (j == n || a[i] != b[j + 1])) j = nxt[j];
if (a[i] == b[j + 1])
++j;
if (j == m) {
++ans;
j = 0;//就多了一行。
}
}
return;
}
这是什么意思呢？
令 \(j=0\) 后，就相当于排除前面的字符串，直接从头重新开始匹配，从而实现删除操作。
一下是完整代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define N 1010
using namespace std;
int nxt[N], n, m, ans = 0;
char a[N], b[N];
void get_next() {
nxt[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
while (j > 0 && b[i] != b[j + 1]) j = nxt[j];
if (b[i] == b[j + 1])
++j;
nxt[i] = j;
}
return;
}
void kmp() {
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && (j == n || a[i] != b[j + 1])) j = nxt[j];
if (a[i] == b[j + 1])
++j;
if (j == m) {
++ans;
j = 0;
}
}
return;
}
int main() {
while (1) {
ans = 0;
scanf("%s", a + 1);
n = strlen(a + 1);
if (a[1] == ‘#‘ && n == 1)
break;
scanf("%s", b + 1);
m = strlen(b + 1);
get_next();
kmp();
printf("%d\n", ans);
}
return 0;
}
#10045 「一本通 2.2 练习 1」Radio Transmission
最小循环节会不会？不会。滚请自行百度。
既然大家都会最小循环节，那这就是水题啦。
原本答案为 (n-next[n])%n==0?n-next[n]:0 现在为 n-next[n]。（想一想为什么）
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define N 1000010
using namespace std;
int nxt[N], n;
char s[N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
nxt[1] = 0;
for (int i = 2, j = 0; i <= n; i++) {
while (j > 0 && s[i] != s[j + 1]) j = nxt[j];
if (s[i] == s[j + 1])
++j;
nxt[i] = j;
}
printf("%d\n", n - nxt[n]);
return 0;
}
警告：下面三道题都是神仙题（但是因为我竟然会做，所以就是水题啦），萌新慎入。
#10046 「一本通 2.2 练习 2」OKR-Periods of Words
首先，你要读懂题...。
题目要求的是求出最大周期长度之和。
\(A\) 为 \(B\) 的最大周期长度，当且仅当 \(A\) 为 \(B\) 的前缀（\(0<|A|<|B|\)），且 \(B\) 为多个 \(A\) 组成的字符串的前缀。
然后经过简单的分析：
最大周期长度 = 总长度 - 最小前缀后缀
自证不难。
那么问题就变为了求最小前缀后缀。
通过 KMP，我们会 \(O(N)\) 求最大前缀后缀，那么最小前缀后缀其实就是 \(\underbrace{next[next[next[...next[i]]]]}_{k个next}\)。
就这么递归下去，最坏时间复杂度为：\(O(N^2)\)。
所以...，肯定是不行的。
别慌，剖析每一次的递归，发现除了最后一个 \(next[]\)，另外 \(k-1\) 个早就计算过了，所以记录下来就可以啦。
然后就变成了 \(O(N)\) 的复杂度了。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define N 1000010
using namespace std;
int nxt[N], cnt[N], n;
char s[N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
nxt[1] = 0;
for (int i = 2, j = 0; i <= n; i++) {
while (j > 0 && s[i] != s[j + 1]) j = nxt[j];
if (s[i] == s[j + 1])
++j;
nxt[i] = j;
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
if (nxt[i] != 0)
cnt[i] = cnt[nxt[i]];
else
cnt[i] = i;
ans += i - cnt[i];
}
printf("%lld\n", ans);
return 0;
}
#10047 「一本通 2.2 练习 3」似乎在梦中见过的样子
什么鬼名字
就是找一个形如 \(A+B+A\) 的字符串，要求 \(|A|\geq k,|B|\geq 1\)。
其实他的前缀后缀就是 \(A\) 啦（很明显吧），然后就想到了 KMP。
但是注意 \(|B|\geq 1\)，所以 \(|A|\times 2<|S|\)。（\(S\) 为原字符串）
然后...，就是大家最喜欢的暴力时间了，直接枚举串的左端点，KMP 时再枚举右端点。
\(O(N^2)\) 不会 T 吗？\(N\leq 1.5\times 10^4,N^2\leq 225,000,000=2.25\times 10^8\)。勉勉强强吧。（CCF 老爷机就算了）
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define N 15010
using namespace std;
int k, nxt[N], n;
char s[N];
int kmp(char* a) {
nxt[0] = nxt[1] = 0;
int len = strlen(a + 1);
int sum = 0, f;
for (int i = 2, j = 0; i <= len; i++) {
while (j > 0 && a[i] != a[j + 1]) j = nxt[j];
if (a[i] == a[j + 1])
++j;
f = nxt[i] = j;
while (f * 2 >= i) f = nxt[f];
if (f >= k)
++sum;
}
return sum;
}
int main() {
scanf("%s", s + 1);
scanf("%d", &k);
n = strlen(s + 1);
int ans = 0;
for (int i = 0; i < n; i++) {
ans += kmp(s + i);
}
printf("%d\n", ans);
return 0;
}
#10048 「一本通 2.2 练习 4」Censoring
KMP 的题目怎么能用 KMP 做呢
发现这同样是一道删除类的题目，但是要求输出删除后的结果。[麻烦.jpg]
我们发现，删掉一段 T 之后，被删除的部分前面的一段可能和后面的一段连接起来出现新的 T 。
所以我们删掉一段 T 之后应该接着被删除的位置之前的继续向后匹配。
那么我们维护一个栈，匹配时如果栈顶出现了 T ，就弹出 T 个字符，然后继续从新的栈顶向后匹配就可以了。
匹配使用 KMP 算法。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxL = 1000000 + 5;
int l, lt, Top;
int Next[MaxL], f[MaxL];
char S[MaxL], T[MaxL], Str[MaxL];
void Prepare()
{
int j = Next[1] = 0;
for (int i = 2; i <= lt; ++i)
{
while (j > 0 && T[j + 1] != T[i]) j = Next[j];
if (T[j + 1] == T[i]) ++j;
Next[i] = j;
}
}
int main()
{
scanf("%s%s", S + 1, T + 1);
l = strlen(S + 1); lt = strlen(T + 1);
Prepare();
int j = 0;
for (int i = 1; i <= l; ++i)
{
Str[++Top] = S[i];
while (j > 0 && T[j + 1] != Str[Top]) j = Next[j];
if (T[j + 1] == Str[Top]) ++j;
if (j == lt)
{
Top -= lt;
j = f[Top];
}
else f[Top] = j;
}
Str[Top + 1] = 0;
printf("%s\n", Str + 1);
return 0;
}
以上内容转载自这篇文章。
然后是乱搞方法：
字符串 Hash，同样维护一个栈，但是用字符串哈希来比对。
优点：
缺点：
但是在能过的基础上，字符串哈希肯定是首选。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#define N 1000010
#define base 13331ULL
using namespace std;
typedef unsigned long long ull;
int n, m, tot = 0;
ull p[N], f[N], ha, jl;
char a[N], b[N], ans[N];
int main() {
scanf("%s", a + 1);
scanf("%s", b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
p[0] = 1;
for (int i = 1; i <= m; i++) {
p[i] = p[i - 1] * base;
ha = ha * base + b[i] - ‘a‘ + 1;
}
for (int i = 1; i <= n; i++) {
ans[++tot] = a[i];
f[tot] = f[tot - 1] * base + a[i] - ‘a‘ + 1;
if (tot - m < 0)
continue;
if (f[tot] - f[tot - m] * p[m] == ha)
tot -= m;
}
for (int i = 1; i <= tot; i++) printf("%c", ans[i]);
printf("\n");
return 0;
}
原文：https://www.cnblogs.com/lpf-666/p/12667996.html