题目描述
难度分:2200
输入长度≤125000的字符串s,和长度≤|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
真难啊,首先要观察到如下事实:
- 将字符i改成j与将字符j改成字符i的效果是一样的,所以可以直接考虑i<j的情况。
- 将所有i改成j,再把所有j改成k,与直接把i和j都改成k效果一样。
- 一共只有6种字母,因此最多6次操作必然能够使得s′=t。
所以可以枚举将每个字符i改成字符j,将a
~f
划分为若干集合,每个集合中的字符要改成一样的,一共有203种情况。用递归函数dfs(c,sz)来求所有集合,c从a
开始,初始情况下sz=0,表示当前已经划分出了几个集合,每一层递归可以将当前字符c放入到新的集合sz中,也可以将c放入到已有的[0,sz)集合中。用一个map构建映射“字母→该字母的分组编号”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(Σ!),其中Σ为字符集大小,本题中Σ=6。每个方案需要在s上进行一次t的匹配,用KMP算法时间复杂度为O(n+m)。因此,整个算法的时间复杂度为O(Σ!(n+m))。
空间复杂度
递归深度为O(Σ);mp映射的空间也是O(Σ);每次到达递归头的时候需要进行字符串匹配,KMP算法的空间消耗在于next数组,本题的next数组是基于t串求的,空间复杂度为O(m)。因此,整个算法的额外空间复杂度为O(Σ+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;
}