J. Spelling Check - 题解
比赛与标签
比赛: School Team Contest 1 (Winter Computer School 2010/11) 标签: hashing, implementation, strings 难度: *1500
题目大意喵~
主人Sama，你好呀！这道题是关于一个叫 Petya 的小迷糊蛋的故事呐。他在打字的时候，总是会手滑多按一个键，导致单词里多出一个字母的说。
我们的任务就是帮他写一个程序，给他两个字符串，第一个是Petya打错的词 s，第二个是字典里的正确单词 t。我们知道 s 恰好比 t 多一个字符。我们需要找出 s 中所有可能的位置，只要删掉那个位置的字符，s 就能变得和 t 一模一样！
最后，我们要先输出总共有多少个这样的位置，然后在下一行按从小到大的顺序输出这些位置（位置是从1开始数的哦）。如果找不到任何一个这样的位置，就只输出一个 0 喵~。
举个栗子：
s= "abdrakadabra"t= "abrakadabra" 只要把s的第3个字符 'd' 删除，s就变成了t。所以答案是 1 个位置，即第 3 位。
解题思路，开始分析咯！
这道题看起来是不是有点棘手呀？字符串长度有 10^6 那么长，如果我们一个一个地去尝试删除 s 中的每个字符，然后把新生成的字符串和 t 比较，那可就太慢啦！(N 个位置 * N 的比较 = O(N^2))，肯定会超时的说！
所以，我们需要一个更聪明的办法，一个线性的 O(N) 解法！让本猫娘来带你分析一下吧~
想象一下，假如我们删除了 s 中间位置为 i 的字符 s[i]（这里的 i 是从0开始的下标哦），使得剩下的字符串恰好等于 t。这意味着什么呢？
这意味着：
s在s[i]之前的部分（前缀），必须和t相应位置的前缀完全一样！也就是s[0...i-1]要等于t[0...i-1]。s在s[i]之后的部分（后缀），必须和t相应位置的后缀完全一样！也就是s[i+1...n-1]要等于t[i...m-1]。（n和m分别是s和t的长度）
哇！问题一下子就被我们分解成了 前缀匹配 和 后缀匹配 两个部分了喵！我们可以分别处理它们，然后再把信息组合起来，这样效率就高多啦！
第一步：处理前缀匹配
我们可以从头开始，比较 s 和 t，看看它们最长公共前缀有多长。用一个指针 l 从 0 开始，只要 s[l] == t[l] 就一直往后走。当 s[l] != t[l] 或者走到头了，l 的值就是它们最长公共前缀的长度。
这个 l 有什么用呢？如果我们要删除的字符位置 i 大于 l，那说明 s[0...i-1] 这个前缀里包含了 s[l] 这个不匹配的字符，它肯定不可能和 t[0...i-1] 相等啦。所以，所有可能成为答案的删除位置 i，都必须满足 i <= l！
第二步：处理后缀匹配
前缀搞定了，后缀也用类似的思路！我们可以从后往前看，预处理出对于 t 的每一个位置 j，t 从 j 开始的后缀 t[j...m-1] 和 s 对应的后缀 s[j+1...n-1] 的公共部分有多长。
我们可以用一个数组 d 来存这个信息，d[j] 表示 s 从 j+1 开始的后缀和 t 从 j 开始的后缀能够匹配上的长度。这个可以用动态规划（或者说递推）的思想，从后往前计算：
d[m] = 0(空后缀匹配长度为0)- 如果
s[j+1] == t[j]，那么d[j] = d[j+1] + 1 - 否则，
d[j] = 0
第三步：组合信息，找出答案！
现在我们有了所有需要的信息啦！我们遍历所有可能的删除位置 i（从0到m），对于每个 i，我们检查：
- 前缀条件：
i <= l是否成立？ - 后缀条件：
s从i+1开始的后缀s[i+1...n-1]是否和t从i开始的后缀t[i...m-1]完全匹配？t的这个后缀长度是m-i。所以我们只需要检查我们预处理好的d[i]是否等于m-i就好了！
如果这两个条件同时满足，那么删除 s 的第 i+1 个字符（下标为 i）就是一组合法的解！我们把它记下来。
这样，我们通过两次线性扫描（一次前缀，一次后缀）和一次最终检查，就把问题在 O(N) 的时间内解决了，是不是很优雅呢？喵~
代码实现 (附上注释喵~)
#include <iostream>
#include <vector>
#include <string>
// 使用 using namespace std; 可以让代码更简洁一些，但在大项目中要小心命名冲突哦
using namespace std;
int main() {
// 这两行是C++的加速黑魔法，让cin和cout变得和闪电一样快！喵~
// 对于大数据量的输入输出，这个非常重要！
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s, t;
cin >> s >> t; // 读入两个字符串
int n = s.size();
int m = t.size();
// 题目保证 s 比 t 长1，但我们还是检查一下以防万一
if (n != m + 1) {
cout << 0 << endl;
return 0;
}
// 第一步：计算 s 和 t 的最长公共前缀长度 l
int l = 0;
while (l < m && s[l] == t[l]) {
l++;
}
// 第二步：从后往前计算后缀匹配信息
// d[j] 表示 s 的后缀 s[j+1...] 和 t 的后缀 t[j...] 的最长公共前缀长度
// 也就是我们思路里说的后缀匹配长度啦
vector<int> d(m + 1);
d[m] = 0; // base case: 空后缀匹配长度为0
for (int j = m - 1; j >= 0; j--) {
if (s[j + 1] == t[j]) {
// 如果当前字符匹配，那么匹配长度就是后面一位的匹配长度+1
d[j] = 1 + d[j + 1];
} else {
// 如果不匹配，那从这里开始的后缀匹配长度就断了，是0
d[j] = 0;
}
}
// 第三步：遍历所有可能的删除点，结合前后缀信息找出答案
vector<int> candidates; // 用一个vector来存储所有合法的删除位置
for (int j = 0; j <= m; j++) {
// j 是要删除的字符在 s 中的下标 (0-indexed)
// 条件1 (前缀匹配): j <= l
// 要删除的位置必须在 s 和 t 的第一个不同点之前（或就是那个不同点）
// 条件2 (后缀匹配): d[j] == m - j
// s 在删除点之后的整个后缀，必须和 t 在删除点之后的整个后缀完全匹配
// t 的后缀 t[j...] 的长度是 m - j
if (j <= l && d[j] == m - j) {
candidates.push_back(j);
}
}
// 最后，按照格式输出答案
if (candidates.empty()) {
cout << 0 << endl;
} else {
cout << candidates.size() << endl;
for (int i = 0; i < candidates.size(); i++) {
if (i > 0) cout << " ";
// 输出的是位置（1-indexed），所以要 j + 1
cout << candidates[i] + 1;
}
cout << endl;
}
return 0; // 程序顺利结束啦！
}复杂度分析的说
- 时间复杂度: O(N) 的说。其中 N 是字符串
s的长度。我们计算前缀l用了 O(N) 时间，计算后缀匹配数组d用了 O(N) 时间，最后遍历寻找答案也用了 O(N) 时间。总的来说就是线性的，非常快！ - 空间复杂度: O(N) 的说。我们用了一个
vector<int> d来存储后缀匹配信息，它的大小和字符串t的长度成正比，所以空间复杂度是 O(N)。
知识点与总结
这道题真是一道非常棒的字符串入门思维题呢！它教会了我们一个重要的思想：
前后缀分解: 当处理一个修改（比如删除）对整个数据结构（比如字符串）的影响时，可以考虑把问题分解成修改点之前和之后两个独立的部分。通过预处理前后缀的信息，可以快速判断单次修改的合法性。
动态规划/递推: 在计算后缀匹配长度时，我们用到了简单的递推思想。
d[j]的值依赖于d[j+1]，这是典型的DP特征。字符串哈希 (Alternative): 喵~ 偷偷告诉你，这道题的标签里有
hashing，说明它也可以用字符串哈希来解哦！思路是：预处理s和t的所有前缀哈希值。要检查删除s[i]是否可行，我们只需要计算出s的前缀s[0...i-1]和后缀s[i+1...n-1]的哈希值，然后把它们“拼接”起来，看看拼接后的哈希值是否等于t的哈希值。这也是一个 O(N) 的解法，非常酷！
希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问本猫娘~ 祝你AC多多，学习愉快呐！喵~