D. MUH and Cube Walls - 题解
比赛与标签
比赛: Codeforces Round 269 (Div. 2) 标签: string suffix structures, strings 难度: *1800
小猫咪的题目解读喵~
主人，你好呀！今天我们来解决一道非常有趣的题目，就像用积木搭城堡一样，喵~
这道题是说，我们有两面“墙”，一面是熊熊们搭的，有 n 座塔；另一面是叫 Horace 的大象搭的，有 w 座塔。每座塔都有一个高度。
我们的任务是，看看在熊熊那面长长的墙上，有多少个连续的、长度为 w 的片段，可以和大象的墙“匹配”上。
这里的“匹配”有一个特别的规则哦！Horace 可以把他的墙整体向上或向下移动。比如说，Horace 的墙是 [3, 4, 2]，我们可以在熊熊的墙里找到 [5, 6, 4] 这段。你看，虽然每座塔的高度都不同，但它们的高度关系是一样的，对不对？[5, 6, 4] 里的每一座塔都比 [3, 4, 2] 里对应位置的塔正好高了2个单位。就像把 Horace 的墙整体向上平移了2个单位一样，喵~
所以，我们的目标就是找出熊熊墙上有多少个这样的“形状”相同的片段呐。
聪明的猫猫想到了好办法！
直接比较塔的高度太麻烦了，因为它们可以整体上下移动嘛。那我们应该比较什么呢？
猫猫的脑袋里灵光一闪！既然绝对高度不重要，那相对高度是不是就重要了呢？也就是说，相邻塔之间的高度差！
我们来想一下，如果一段墙 a[i...i+w-1] 和 Horace 的墙 b[0...w-1] 形状相同，这意味着存在一个固定的高度差 C，使得对于所有 k (从 0到w-1)，都有 a[i+k] = b[k] + C。
这个式子稍微变一下形，就是 a[i+k] - b[k] = C。也就是说，它们对应位置塔的高度差是一个常数。
那么，对于相邻的两对塔，也应该满足这个关系： a[i+k] - b[k] = Ca[i+k+1] - b[k+1] = C
所以，a[i+k] - b[k] = a[i+k+1] - b[k+1]。 再整理一下，就变成了： a[i+k] - a[i+k+1] = b[k] - b[k+1]
看呐！我们成功把问题转化啦！如果两段墙的“形状”相同，那么它们相邻塔之间的高度差序列一定是完全一样的！
这下问题就清晰多啦：
- 我们先计算出熊熊的墙
a的相邻高度差序列，我们叫它d_a。它的长度是n-1。 - 我们再计算出大象的墙
b的相邻高度差序列，我们叫它d_b。它的长度是w-1。 - 然后，问题就变成了：在序列
d_a中，序列d_b出现了多少次？
这不就变成了经典的字符串匹配问题了嘛！我们可以把 d_a 当作文本串，d_b 当作模式串。要高效地解决这个问题，KMP算法就是我们的不二之选啦！
在动手之前，还有两个小小的特殊情况要考虑哦：
- 如果
w > n，大象的墙比熊熊的墙还长，那肯定一次都匹配不上，答案是0。 - 如果
w = 1，大象的墙只有一座塔。那它可以和熊熊墙上的任何一座塔匹配，因为没有相邻的塔可以形成“形状”，所以答案就是n啦。
总结一下我们的解题步骤：
- 处理
w > n和w = 1的边界情况。 - 对于一般情况，将
a数组和b数组分别转化为差分数组d_a和d_b。 - 使用 KMP 算法，在文本串
d_a中查找模式串d_b的出现次数。
是不是感觉思路一下子就清晰了呢？喵~
猫娘的代码魔法时间~
下面就是实现这个思路的代码啦，我已经加上了详细的注释，主人可以看看哦！
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 加速输入输出，让程序跑得更快喵~
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, w;
cin >> n >> w;
vector<long long> a(n);
vector<long long> b(w);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < w; i++) {
cin >> b[i];
}
// 处理边界情况喵~
if (w == 1) {
// 如果模式墙只有1座塔，它可以匹配任何1座塔
cout << n << '\n';
} else if (w > n) {
// 模式墙比主墙还长，不可能匹配上
cout << 0 << '\n';
} else {
// --- 问题转化：计算差分数组 ---
// 熊熊墙的差分数组 d_a，长度为 n-1
vector<long long> d_a(n - 1);
for (int i = 0; i < n - 1; i++) {
d_a[i] = a[i] - a[i + 1];
}
// 大象墙的差分数组 d_b，长度为 w-1，这就是我们的“模式串”
vector<long long> d_b(w - 1);
for (int i = 0; i < w - 1; i++) {
d_b[i] = b[i] - b[i + 1];
}
// --- KMP 算法核心部分 ---
// 1. 预处理：为模式串 d_b 计算 prefix (next) 数组
int m = w - 1; // 模式串的长度
vector<int> prefix(m, 0);
int len = 0; // 当前已匹配的前缀长度
int i_val = 1;
while (i_val < m) {
if (d_b[i_val] == d_b[len]) {
len++;
prefix[i_val] = len;
i_val++;
} else {
if (len != 0) {
// 失配了，根据 prefix 数组回溯
len = prefix[len - 1];
} else {
// 已经是最长前缀的开头了，还是没匹配上
prefix[i_val] = 0;
i_val++;
}
}
}
// 2. 匹配过程：在 d_a 中寻找 d_b
int j = 0; // 指向模式串 d_b 的指针
int count = 0; // 匹配成功的次数
for (int i = 0; i < n - 1; i++) {
// 如果失配，利用 prefix 数组移动模式串指针 j
while (j > 0 && d_a[i] != d_b[j]) {
j = prefix[j - 1];
}
// 如果当前字符匹配成功，移动模式串指针 j
if (d_a[i] == d_b[j]) {
j++;
}
// 如果 j 到达模式串末尾，说明找到一个完整匹配
if (j == m) {
count++;
// 继续寻找下一个可能的匹配（处理重叠情况）
j = prefix[j - 1];
}
}
cout << count << '\n';
}
return 0;
}效率分析，一点都不难哦！
时间复杂度: O(n + w) 的说 为啥呢？计算两个差分数组
d_a和d_b分别需要遍历一次a和b，时间是 O(n) + O(w)。之后 KMP 算法的预处理部分（计算prefix数组）时间复杂度是 O(w)，匹配过程的时间复杂度是 O(n)。所以总的时间复杂度就是 O(n + w) 啦，非常高效！空间复杂度: O(n + w) 的说 我们主要需要空间来存储两个原始数组
a和b，还有它们的差分数组d_a和d_b，以及 KMP 的prefix数组。所以总的空间开销和输入规模是线性相关的，也就是 O(n + w) 的说。
猫娘的小课堂总结喵~
主人是不是又学到了新知识呀？这道题真的非常巧妙，我们来总结一下核心的知识点吧！
差分思想 (Problem Transformation) 这道题最最核心的技巧就是“差分思想”！它教会我们，当遇到与绝对值无关、只与相对关系有关的问题时，可以尝试计算相邻元素的差值，把问题转化成我们更熟悉的形式。把对“形状”的模糊匹配，转化为了对“差分序列”的精确匹配，一下子就让问题变简单了呢。
KMP 算法 转化后的问题是一个经典的字符串匹配问题，KMP 算法是解决这类问题的标准高效方案。它通过预处理模式串，得到一个
prefix(或next) 数组，在匹配失败时可以智能地“跳跃”，避免了暴力匹配中大量的重复比较，将时间复杂度降到了线性级别。边界条件处理 小细节决定成败！
w=1的情况，是无法形成“差分”的，所以需要单独拿出来处理哦。w > n的情况更简单啦，小片段塞不进大序列里，直接判断就好，喵~
希望这篇题解能帮助到主人！多多练习，你也能成为算法大师的！加油喵~