BZOJ4503:两个串(bitset字符串匹配)

题意

题目链接

Sol

Orz xudyh

F个毛T啊。。直接bitset一波就赢了啊。。。(虽然复杂度很假)

就是记录匹配串中每个元素出现的位置，将第(i)个位置的bitset右移(i)位后与起来

最后找1出现的位置就行了

复杂度：(O(frac{n^2}{32}))

#includeusing namespace std;const int MAXN = 1e5 + 10;int N, M, cnt;char S[MAXN], T[MAXN];bitset B[28];main() {    scanf("%sn%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 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("%dn", cnt);    for(int i = 1; i <= N - M + 1; i++) if(ans[i] == 1) printf("%dn", i - 1);}/*ababababbaa?aba?abba*/