题目描述

难度分:$2200$

输入长度$\leq 125000$的字符串$s$，和长度$\leq |s|$的字符串$t$，只包含前六个小写英文字母。

定义$f(S,T)$为使$S=T$的最小操作次数。其中每次操作，你可以选择一个字母$x$和另一个字母$y$，然后把$S$和$T$中的所有字母$x$替换成字母$y$。

对于$s$中的每个长为$|t|$的子串$s’$，输出$f(s’,t)$。

输入样例

abcdefa
ddcb

输出样例

2 3 3 3 

算法

枚举+$KMP$

真难啊，首先要观察到如下事实：

1. 将字符$i$改成$j$与将字符$j$改成字符$i$的效果是一样的，所以可以直接考虑$i \lt j$的情况。
2. 将所有$i$改成$j$，再把所有$j$改成$k$，与直接把$i$和$j$都改成$k$效果一样。
3. 一共只有$6$种字母，因此最多$6$次操作必然能够使得$s’=t$。

所以可以枚举将每个字符$i$改成字符$j$，将a~f划分为若干集合，每个集合中的字符要改成一样的，一共有$203$种情况。用递归函数$dfs(c,sz)$来求所有集合，$c$从a开始，初始情况下$sz=0$，表示当前已经划分出了几个集合，每一层递归可以将当前字符$c$放入到新的集合$sz$中，也可以将$c$放入到已有的$[0,sz)$集合中。用一个$map$构建映射“字母$\rightarrow$该字母的分组编号”$mp$。

当$c=$g时，前$6$个字母已经考虑完，递归就到头了，基于当前的映射方案对$s$和$t$跑字符串匹配算法。这里用$KMP$算法，先对$t$串求$next$数组，然后在$s$串上利用映射方案$mp$匹配$t$串，每在$s$的一个位置$st$匹配到了$t$，就更新答案$ans[st]=max(ans[st],sz)$，此时说明了划分了$sz$个集合出来，每个集合都对应着一次操作，那肯定是集合越多越好，最终的答案就是$6-ans[st]$。

复杂度分析

时间复杂度

递归求所有映射方案的时间复杂度为$O(\Sigma!)$，其中$\Sigma$为字符集大小，本题中$\Sigma=6$。每个方案需要在$s$上进行一次$t$的匹配，用$KMP$算法时间复杂度为$O(n+m)$。因此，整个算法的时间复杂度为$O(\Sigma!(n+m))$。

空间复杂度

递归深度为$O(\Sigma)$；$mp$映射的空间也是$O(\Sigma)$；每次到达递归头的时候需要进行字符串匹配，$KMP$算法的空间消耗在于$next$数组，本题的$next$数组是基于$t$串求的，空间复杂度为$O(m)$。因此，整个算法的额外空间复杂度为$O(\Sigma+m)$。

C++ 代码

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

using namespace std;

void solve() {
    string s, t;
    cin >> s >> t;
    int m = t.size();
    vector<int> ans(s.size() - m + 1, 0);
    vector<int> mp(127, 0);
    function<void(int, int)> dfs = [&](int c, int sz) {
        if(c == 'g') {
            vector<int> pi(m);
            int j = 0;
            for(int i = 1; i < m; ++i) {
                int v = mp[t[i]];
                while(j > 0 && mp[t[j]] != v) {
                    j = pi[j - 1];
                }
                if(mp[t[j]] == v) {
                    ++j;
                }
                pi[i] = j;
            }
            j = 0;
            for(int i = 0; i < s.size(); ++i) {
                int v = mp[s[i]];
                while(j > 0 && mp[t[j]] != v) {
                    j = pi[j - 1];
                }
                if(mp[t[j]] == v) {
                    ++j;
                }
                if(j == m) {
                    int st = i - m + 1;
                    ans[st] = max(ans[st], sz);
                    j = pi[j - 1];
                }
            }
            return;
        }
        mp[c] = sz;
        dfs(c + 1, sz + 1);
        for(int j = 0; j < sz; ++j) {
            mp[c] = j;
            dfs(c + 1, sz);
        }
    };
    dfs('a', 0);
    for(int v : ans) {
        cout << 6 - v << " ";
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}