思路与算法

将每个串编码为距同字符上次出现的距离，首次出现编码0。若模式第k位编码为0，则当前文本距离为0或大于k（先前字符在窗口外）才匹配；否则距离必须完全相等。用这个相对窗口判定构造参数化前缀函数，再按KMP扫描文本并输出全部起点。

正确性说明

两个等长串可通过字符置换互相得到，当且仅当字符相等关系在各位置完全相同。前驱距离精确刻画这种关系：模式中首次字符在文本当前窗口内也必须首次出现，非首次则必须引用同样的前位置。这个条件也适用于计算前缀与后缀的同构边界；失配回退后用新的k重新解释窗口外距离，因此保留的前缀关系仍准确。每个完整匹配恰为一个可扩展到全字符集排列的单射映射。

复杂度

每组O(n+m+C)时间、O(n+m+C)空间，含last数组清零和前驱距离/前缀表初始化。n,m,C≤10^6，T=3。匹配位置数组最多n项，索引均用int足够。

易错点

不能直接要求距离0等于0：一个字符在整个文本出现过，但在当前窗口外，仍可视作窗口首次。每次回退k后都要重新判定distance>k。n<m时输出0及空第二行。独立双向字典逐窗核验，另做5000次随机对拍和植入必有解的重命名窗口。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, C;
    cin >> T >> C;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> last(C + 1), s(n), p(m), pi(m);
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            s[i] = last[x] ? i + 1 - last[x] : 0;
            last[x] = i + 1;
        }
        fill(last.begin(), last.end(), 0);
        for (int i = 0, x; i < m; ++i) {
            cin >> x;
            p[i] = last[x] ? i + 1 - last[x] : 0;
            last[x] = i + 1;
        }
        auto match = [&](int distance, int k) {
            return p[k] == 0 ? (distance == 0 || distance > k) : distance == p[k];
        };
        for (int i = 1, j = 0; i < m; ++i) {
            while (j && !match(p[i], j))
                j = pi[j - 1];
            if (match(p[i], j))
                ++j;
            pi[i] = j;
        }
        vector<int> answer;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j && !match(s[i], j))
                j = pi[j - 1];
            if (match(s[i], j))
                ++j;
            if (j == m) {
                answer.push_back(i - m + 2);
                j = pi[j - 1];
            }
        }
        cout << answer.size() << '\n';
        for (size_t i = 0; i < answer.size(); ++i)
            cout << answer[i] << (i + 1 == answer.size() ? '\n' : ' ');
        if (answer.empty())
            cout << '\n';
    }
}