思路与算法

将模式和文本编码为相同字符上次出现的距离。参数化KMP在模式距离为0时允许文本距离为0或大于当前匹配长度，否则要求距离相等。每个候选窗口得到字母双射f，再检查所有已定义的f(f(c))均等于c。

正确性说明

距离条件等价窗口中字符相等关系一致，所以KMP不会漏掉任何重命名匹配。双射可扩展为交换若干字母，当且仅当它能补成长度为1或2的置换环；已有两步映射不返回自身正是唯一障碍，故第二次检查充要。

复杂度

读入及距离数组初始化O(n+m)，KMP O(n+m)，候选窗口至多n个，每个检查26字母，总O(n+m+26n)时间，O(n+m)空间。

易错点

前驱在窗口外视为未出现。不能仅检查双射，长度3以上的置换环不符合一次交换规则。模式比文本长时没有答案。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    string S, T;
    cin >> n >> m >> S >> T;
    vector<int> s(n), p(m), pi(m);
    array<int, 26> last{}, first;
    first.fill(-1);
    for (int i = 0; i < n; i++) {
        int c = S[i] - 'a';
        s[i] = last[c] ? i + 1 - last[c] : 0;
        last[c] = i + 1;
    }
    last.fill(0);
    for (int i = 0; i < m; i++) {
        int c = T[i] - 'a';
        p[i] = last[c] ? i + 1 - last[c] : 0;
        last[c] = i + 1;
        if (first[c] < 0)
            first[c] = i;
    }
    auto match = [&](int d, int k) {
        return p[k] == 0 ? (d == 0 || d > k) : d == 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> ans;
    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) {
            int start = i - m + 1;
            array<int, 26> f;
            f.fill(-1);
            for (int c = 0; c < 26; c++)
                if (first[c] >= 0)
                    f[c] = S[start + first[c]] - 'a';
            bool ok = true;
            for (int c = 0; c < 26; c++)
                if (f[c] >= 0 && f[f[c]] >= 0 && f[f[c]] != c)
                    ok = false;
            if (ok)
                ans.push_back(start + 1);
            j = pi[j - 1];
        }
    }
    cout << ans.size() << '\n';
    for (size_t i = 0; i < ans.size(); i++)
        cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');
    if (ans.empty())
        cout << '\n';
}