题目链接CF533F Encoding
提示1：\(\mathcal O(26^2*n)\) 的算法可通过。常用的几种字符串匹配算法kmp，AC自动机，哈希都可以解决该问题 （后两者可以优化到 \(\mathcal O(26*n)\) ）。
提示2：将文本串 \(S\) 和模式串 \(T\) 中的 \(26\) 个字母分开考虑，各自匹配。
\(\mathcal O(26^2*n)\) 的kmp匹配枚举每一种转换，记为 \((x,y),x,y\in\{'a','b',\cdots,'z'\}\)，\(x\) 可以等于 \(y\) ，即不转换。如果该转换在某区间 \(S[l,r]\) 是与 \(T\) 匹配的，则说明在 \(S[l,r]\) 中每个 \(x\) 位置和 \(T\) 中 \(y\) 位置一一对应，每个 \(y\) 位置和 \(T\) 中 \(x\) 位置一一对应，而且不会有另一个关于 \(x\) 的转换使得该区间匹配。 若对于 \(S[l,r]\) 段上 \(x\) 的任何一种转换都不能与 \(T\) 匹配，则说明该段无法匹配；否则在该区间起点打标记，表示该转换匹配成功。对于 \(T\) 任何一个字符 \(x\) 都需要有转换在 \(S[l,r]\) 中匹配，才说明 \(S[l,r]\) 是与 \(T\) 匹配的。
具体实现时令 \(T\) 中 \(x,y\) 互换，其他位置替换为 \(0\)，\(S\) 中除 \(x,y\) 以外的位置置为 0，其它保持不变，这样可以用kmp判断转换 \((x,y)\) 是否与 \(S\) 上某一段匹配。例如：
原字符串 转换 \((b,c)\) ,变成只含 \(0,b,c\) 的序列（只在 \(T\) 转换 \((b,c)\)）\(S\) \(abcab\) \(0~b~c~0~b\)
\(T\) \(acbac\) \(0~b~c~0~b\)
这里 \(a,b,c\) 都能找到转换与 \(S\) 匹配（\(a\) 不转换就可以匹配），而对于 \(S,T\) 都没出现的字母，任意转换都是匹配的，即会把两个序列都变成全 \(0\) ，肯定是匹配的。
\(Code:\) #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int sl,tl,nxt[N],ss[N],tt[N]; bool p[N][27];//p[i][j]标记S[i,i+tl-1]这段上是否有关于x的转换使得与T串匹配 char s[N],t[N]; vector<int>ans; int main() { scanf("%d %d %s %s",&sl,&tl,s+1,t+1); for(int x = 'a'; x <= 'z'; x++){ for(int y = x; y <= 'z'; y++){ //t中x，y互换 for(int i = 1;i <= tl;i++) { if(t[i] == x) tt[i] = y; else if(t[i] == y) tt[i] = x; else tt[i] = 0; } for(int i = 1; i <= sl; i++) ss[i] = ( (s[i] == y)||(s[i] == x) )? s[i] : 0; //kmp匹配 for(int i = 2,j = 0; i <= tl; i++){ while(j && tt[i] != tt[j + 1]) j = nxt[j]; if(tt[i] == tt[j + 1]) nxt[i] = ++j; else nxt[i] = 0; } for(int i = 1,j = 0; i <= sl; i++){ while(j && ss[i] != tt[j + 1]) j = nxt[j]; if(ss[i] == tt[j + 1]) ++j; if(j == tl) { p[i-tl+1][x-'a'] = 1; p[i-tl+1][y-'a'] = 1; j = nxt[j]; } } } } //O(26*n) 的判断：S[i,i+tl-1]是否可以和转换后的T匹配,要满足t的每个字符j都有转换与S[i,i+tl-1]匹配 for(int i = 1;i <= sl-tl+1;i++) { int flag = 1; for(int j = 0;j < 26;j++) if(!p[i][j]) { flag = 0;break;} if(flag) ans.push_back(i); } printf("%d\n",ans.size()); for(auto it : ans) printf("%d ",it); return 0; } \(\mathcal O(26*n)\) 的哈希匹配在kmp匹配结束后，有一个 \(\mathcal O(26*n)\) 的判断循环，因为在kmp中已经求出 \(p_{i,j}\) 的值了，所以对于每个 \(i\) ,有 \(26\) 次 \(\mathcal O(1)\) 的判断 。我们考虑，哈希也可以 \(\mathcal O(1)\) 的判断两个串是否匹配，这里只要将 \(26\) 个字母分别求哈希值再求和匹配就可以了，所以哈希是可以将整体复杂度优化到 \(\mathcal O(26*n)\) 的。
具体实现时需要求出一个特殊的数组，我们记为 \(nxt_{i,j}\) ，表示 \(S[i,|s|]\) 上第一次出现字符 \(j\) 的下标。这样在我们判断 \(S[i,i+|t|-1]\) 这段区间是否可以通过转换 \(j\) 使得与 \(T\) 匹配时，我们先通过 \(nxt_{i,j}\) 获得 \(j\) 下标，如果它在 \([i,i+|t|-1]\) 这个区间上，说明它在 \(T\) 串对应位置有一个字符 \(y\) 需要与它匹配，如果我们把 \([i,i+|t|-1]\) 上的 \(j\) 全部替换为 \(y\) ，其他字符置为 \(0\) 。对所有的 \(26\) 个字符都这样处理，他们分别计算的哈希值加起来与 \(T\) 的哈希值比较，就可以知道 \(S[i,i+|t|-1]\) 是否可以和 \(T\) 匹配了。这样对于每个 \(i\) 的 \(26\) 次计算都是 \(\mathcal O(1)\) 的。注意对于同一区间上的字符转换不能有交集，即两个关于 \(x\) 的转换 \((x,y),(x,z),y\not=z\) 不能同时存在，代码中用 \(vis\) 记录每个字符的转换对象，每个字符的 \(vis_j\) 只能被赋值一次。因为比较懒没写双哈希。
\(Code:\) #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 5; const int base = 131; const int mod = 19260817; int sl,tl,nxt[N][26]; ll T_hash,s_hash[N][26],fac[N]; int vis[27]; vector<int>ans; char s[N],t[N]; int main() { scanf("%d %d %s %s",&sl,&tl,s+1,t+1); fac[0] = 1; for(int i = 1;i <= sl;i++) fac[i] = fac[i-1] * base % mod; //预处理出nxt数组，记录i后第一个字符j的下标 for(int j = 0;j < 26;j++) nxt[sl+1][j] = sl+1; for(int i = sl;i >= 1;i--) for(int j = 0;j < 26;j++){ if(s[i] == j+'a') nxt[i][j] = i; else nxt[i][j] = nxt[i+1][j]; } //求出T串hash值 for(int i = 1;i <= tl;i++) T_hash = (T_hash * base + (t[i]-'a') ) % mod; //求出S串26个字符分开计算的hash值，注意这里是将为j的字符置为1，其他置为0作哈希，之后有（j,y)的转换乘上y即可（哈希满足乘法分配律） for(int i = 1;i <= sl;i++) for(int j = 0;j < 26;j++){ if(s[i] == j+'a') s_hash[i][j] = (s_hash[i-1][j] * base + 1) % mod; else s_hash[i][j] = s_hash[i-1][j] * base % mod; } for(int i = 1;i <= sl-tl+1;i++) { ll tot_hash = 0; memset(vis,-1,sizeof vis); //-1表示未被赋值过 for(int j = 0;j < 26;j++){ int p = nxt[i][j]; if(p > i + tl - 1) continue; int y = t[p-i+1]-'a'; //找到在T串对应位置的字符 //只有之前x,y都没有被转换过才能赋值 if(vis[j] == -1 && vis[y] == -1) vis[y] = j,vis[j] = y; tot_hash = (tot_hash + vis[j] * ((s_hash[i+tl-1][j] - s_hash[i-1][j] * fac[tl]) % mod + mod) ) % mod; } if(tot_hash == T_hash) ans.push_back(i); } printf("%d\n",ans.size()); for(auto it :ans) printf("%d ",it); return 0; } \(\mathcal O(26*n)\) 的AC自动机匹配