题意
题目链接 https://lydsy.com/JudgeOnline/problem.PHP?id=4503
Sol
Orz xudyh
F 个毛 T 啊.. 直接 bitset 一波就赢了啊...(虽然复杂度很假)
就是记录匹配串中每个元素出现的位置, 将第 \(i\) 个位置的 bitset 右移 \(i\) 位后与起来
最后找 1 出现的位置就行了
复杂度:\(O(\frac{n^2}{32})\)
- #include<bits/stdc++.h>
- using namespace std;
- const int MAXN = 1e5 + 10;
- int N, M, cnt;
- char S[MAXN], T[MAXN];
- bitset<MAXN> B[28];
- main() {
- scanf("%s\n%s", S + 1, T + 1);
- N = strlen(S + 1); M = strlen(T + 1);
- for(int i = 1; i <= N; i++) B[S[i] - 'a'].set(i);
- bitset<MAXN> ans; ans.set();
- for(int i = 1; i <= M; i++) if(T[i] != '?') ans &= (B[T[i] - 'a']>> (i - 1));
- for(int i = 1; i <= N - M + 1; i++) if(ans[i] == 1) cnt++; printf("%d\n", cnt);
- for(int i = 1; i <= N - M + 1; i++) if(ans[i] == 1) printf("%d\n", i - 1);
- }
- /*
- ababababba
- a?aba?abba
- */
来源: http://www.bubuko.com/infodetail-2801090.html