BZOJ 4503. 两个串

Description

兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，
分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。

Solution

Code

注意匹配的首位置往后必须有超过T.size()个字符.

#include <bitset>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1000005;

std:: bitset<N> A[26];
int main () {
    std:: string S, T;
    std:: cin >> S >> T;
    for (int i = 0; i < S.size(); i += 1)
        A[S[i] - 'a'].set(i);
    std:: bitset<N> res;
    res.set();
    for (int i = 0; i < T.size(); i += 1)
        if (T[i] != '?')
            res &= (A[T[i] - 'a'] >> i);
    int Res = 0;
    for (int i = 0; i + T.size() - 1 < S.size(); i += 1)
        if (res[i] == 1)
            Res += 1;
    printf("%d\n", Res);
    for (int i = 0; i + T.size() - 1 < S.size(); i += 1) 
        if (res[i])
            printf("%d\n", i);
    return 0;
}

BZOJ 4503. 两个串

原文：https://www.cnblogs.com/qdscwyy/p/9774623.html