思路来自 【题解】Codeforces533F. Encoding 按字符分解，AC自动机 。其实与哈希匹配思想是一致的，都是想要找到一种方式可以做到对于每个起点 \(i\) ，进行 \(26\) 次复杂度只有 \(\mathcal O(1)\) 的判断。我们把 \(T\) 串分成 \(26\) 个 \(01\) 串（不计入全 \(0\) 串），构建AC自动机。再将 \(S\) 串分成 \(26\) 个 \(01\) 串，在AC自动机上作匹配，每次匹配到一个 \(T\) 串末尾，就在该位置标记匹配的字符，对于某个 \(i\) ,要求 \(T\) 中 \(26\) 个字符 \(j\) 都能被匹配到末尾（除 \(j\) 全 \(0\) 串外），才说明该段和 \(T\) 匹配。例如：
原字符串 \(a\) 的 \(01\) 串 \(b\) 的 \(01\) 串 \(c\) 的 \(01\) 串\(S\) \(abcab\) \(1~0~0~1~0\) \(0~1~0~0~1\) \(0~0~1~0~0\)
\(T\) \(acbac\) \(1~0~0~1~0\) \(0~0~1~0~0\) \(0~1~0~0~1\)
这里 \(S\) 的 \(a\) 串会匹配到AC自动机上对应 \(T\) 的 \(a\) 串末端， \(S\) 的 \(b\) 串会匹配到AC自动机上对应 \(T\) 的 \(c\) 串末端， \(c\) 串会匹配到AC自动机上对应 \(T\) 的 \(b\) 串末端，其他全为 \(0\) 的串不插入AC自动机，所以 \(S\) 和 \(T\) 是匹配的。
AC自动机构建复杂度是 \(\mathcal O (26*n)\) 的，匹配时无需暴力跳fail，对于 \(26\) 个串的匹配也是 \(\mathcal O (26*n)\) 。
\(Code:\) #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int sl,tl,tt[N],en[N*26], match[27]; bool has[27]; char s[N],t[N]; vector<int>ans; int trie[N*26][2],cnt,fail[N*26],now[26]; void insert(int o){ int now = 0; for (int i = 1,c; i <= tl;i++){ c = tt[i]; if(trie[now][c] == 0) trie[now][c] = ++cnt; now = trie[now][c]; } en[now] = o; } void build(){ queue<int> q; for (int i = 0; i < 2;i++) if(trie[0][i]) q.push(trie[0][i]); while(!q.empty()){ int now = q.front();q.pop(); for (int i = 0; i < 2;i++){ if(trie[now][i]){ q.push(trie[now][i]); fail[trie[now][i]] = trie[fail[now]][i]; }else trie[now][i] = trie[fail[now]][i]; } } } int main() { scanf("%d %d %s %s",&sl,&tl,s+1,t+1); memset(en,-1,sizeof en); for(int j = 0;j < 26;j++){ for(int i = 1; i <= tl; i++) has[j] |= tt[i] = (t[i] == j + 'a'); if(has[j]) insert(j); //不是全0串才插入AC自动机 } build(); for(int i = 1;i <= sl;i++){ int flag = 0; memset(match,-1,sizeof match); for(int j = 0;j < 26;j++){ int c = s[i]-'a'; now[j] = trie[now[j]][c == j]; if(en[now[j]] != -1) match[en[now[j]]] = j;//记录T末端字符en[now[j]]匹配到S的字符j } for(int j = 0;j < 26;j++) if(has[j]){ if(match[j] == -1) {flag = 1;break;} int y = match[j]; //在T串同时含j,y的情况下，match[j]=y,match[y]=j才满足变换后匹配 if(match[y] != j && has[y]) {flag = 1;break;} } if(!flag) ans.push_back(i-tl+1); } printf("%d\n",ans.size()); for(auto it : ans) printf("%d ",it); return 0; }这道题可以用多种算法尝试解决，是一道很全面的题目。各算法运行结果如下（空间换时间了）：