这道题 LeetCode 438《找到字符串中所有字母异位词》是滑动窗口思想的集大成者，它结合了之前《字符串的排列》的判断逻辑，并要求找出所有满足条件的位置。这在NOI/CSP中是非常高频的考点。

第一部分：题目描述 (NOI风格)

题目名称： 找到字符串中所有字母异位词 (Find All Anagrams in a String) 输入文件： anagrams.in 输出文件： anagrams.out 时间限制： 1.0 s 空间限制： 256 MB

【题目描述】

给定两个字符串 $S$ 和 $P$。请找出字符串 $S$ 中所有是 $P$ 的 字母异位词 的 子串 的起始索引（下标从 0 开始）。

定义说明：

1. 字母异位词 (Anagram)：如果两个字符串包含的字符种类和数量都完全相同，只是顺序不同，则称它们互为字母异位词。例如，"abc" 和 "cba" 互为字母异位词。
2. 子串 (Substring)：是字符串中连续的一段字符序列。

【输入格式】

输入文件包含两行： 第一行包含一个字符串 $S$。 第二行包含一个字符串 $P$。 两个字符串均只包含小写英文字母。

【输出格式】

输出一行，包含所有满足条件的起始索引，按升序排列，索引之间用一个空格隔开。 如果不存在任何满足条件的子串，则输出一个空行。

【输入样例 1】

cbaebabacd
abc

【输出样例 1】

0 6

(说明：索引从0开始的子串是 "cba"，它是 "abc" 的异位词。索引从6开始的子串是 "bac"，也是 "abc" 的异位词。)

【输入样例 2】

abab
ab

【输出样例 2】

0 1 2

(说明：索引0的 "ab"，索引1的 "ba"，索引2的 "ab" 都是 "ab" 的异位词。)

【数据范围与提示】

• $1 \le |P|, |S| \le 3 \times 10^4$
• 字符串仅包含小写英文字母 ('a'-'z')。

第二部分：教练辅导时间

1. 思路提示 (Hint)

• 核心关联：这道题和我们之前讲的《字符串的排列》几乎一模一样。那道题是问“存不存在”，这道题是问“所有存在的位置在哪里”。
• 固定大小的窗口：我们要找的子串，长度一定等于 $|P|$。这是一个非常强烈的信号，提示我们应该使用一个固定大小的滑动窗口。
• 高效判断：如何在窗口滑动的每一步，都高效地判断窗口内的子串是不是 $P$ 的异位词？我们不需要每次都重新统计整个窗口，只需要关注滑进来和滑出去的那两个字符。

2. 预备知识点 (Prerequisites)

• 滑动窗口算法 (Sliding Window)：必须熟练掌握其思想和代码框架。
• 哈希/计数数组：使用 int cnt[26] 来高效统计和比较字符频率。
• 向量 (Vector)：用于存储结果，并方便地进行输出。

3. 启发式教学与草稿纸推演 (Heuristic Approach)

来，拿出草稿纸，这和上次的推演非常像，但这次我们的目标是记录所有匹配的时刻。

场景设置：

• $S = \text{"cbaebabacd"}$
• $P = \text{"abc"}$

第一步：制作“目标指纹”

• 统计 $P$ 的字符频率：cnt_p = {a:1, b:1, c:1}
• 确定窗口长度：$L = 3$

第二步：初始化窗口并开始滑动

图形化思考： 滑动窗口就像一个模板或者一个筛子。

1. 我们先用 $P$ 制作一个特定形状的“模板”（cnt_p）。
2. 然后我们把这个模板覆盖在 $S$ 的开头。
3. 检查模板下的区域是否和模板完全吻合。
4. 然后把模板向右平移一格，再检查，再平移...直到结尾。
5. 平移时，我们只需要更新模板边缘变化的部分，而不需要重新审视整个模板覆盖的区域。

4. 复杂度分析

• 时间复杂度：
  • 预处理 $P$ 的计数数组：$O(|P|)$。
  • 初始化第一个窗口的计数数组：$O(|P|)$。
  • 滑动过程：循环了 $|S| - |P|$ 次。
  • 每次循环内部：更新两个字符的计数（$O(1)$），比较两个计数数组（$O(\Sigma)$，其中 $\Sigma=26$）。
  • 总时间：$O(|P| + (|S|-|P|) \cdot \Sigma)$。因为 $\Sigma$ 是常数，所以复杂度为 $O(|S|)$。
• 空间复杂度：
  • 我们使用了两个大小为 26 的计数数组。
  • 以及一个 vector 存储答案。在最坏情况下（如 S="ababab", P="ab"），答案数量级是 $O(|S|)$。
  • 因此，辅助空间复杂度为 $O(\Sigma)$，如果考虑存储答案的空间，则为 $O(|S|)$。在竞赛中，通常只计算算法运行所需的辅助空间，即 $O(\Sigma)$ 或 $O(1)$。

第三部分：标准题解代码 (NOI C++14)

/*
 * 题目：找到字符串中所有字母异位词
 * 来源：改编自 LeetCode 438
 * 算法：滑动窗口 + 计数数组
 * 时间复杂度：O(|S|)，其中 |S| 是主串长度
 * 空间复杂度：O(1) (辅助空间)
 */

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // I/O 加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, p;
    if (!(cin >> s >> p)) return 0;

    int n = s.length();
    int m = p.length();

    // 【易错点1】边界检查：如果模式串比主串还长，不可能有匹配
    if (m > n) {
        // 输出空行
        cout << endl;
        return 0;
    }

    vector<int> cnt_p(26, 0);
    vector<int> cnt_s(26, 0);
    vector<int> ans;

    // 1. 预处理：统计 p 的频率 和 s 的第一个窗口的频率
    for (int i = 0; i < m; ++i) {
        cnt_p[p[i] - 'a']++;
        cnt_s[s[i] - 'a']++;
    }

    // 2. 检查第一个窗口
    if (cnt_p == cnt_s) {
        ans.push_back(0);
    }

    // 3. 开始滑动窗口
    // 窗口的右端点从 m 移动到 n-1
    for (int i = m; i < n; ++i) {
        // 【核心】窗口向右滑动一格
        // 新字符进入窗口：s[i]
        cnt_s[s[i] - 'a']++;
        // 旧字符离开窗口：s[i-m]
        cnt_s[s[i - m] - 'a']--;

        // 检查当前窗口是否匹配
        if (cnt_p == cnt_s) {
            // 【易错点2】记录的是窗口的起始索引，不是右端点 i
            // 当前窗口是 [i-m+1, i]，所以起始索引是 i-m+1
            ans.push_back(i - m + 1);
        }
    }

    // 4. 按格式输出结果
    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
    }
    cout << endl; // 即使没有答案，也要输出一个换行符，形成空行

    return 0;
}