51nod 1532 带可选字符的多字符串匹配（位运算）

题意：

有一个文本串，它的长度为m (1 <= m <= 2000000)，现在想找出其中所有的符合特定模式的子串位置。
符合特定模式是指，该子串的长度为n (1 <= n <= 500)，并且第i个字符需要在给定的字符集合Si中。
因此，描述这一特定模式，共需要S1，S2，...，Sn这n个字符集合。每个集合的大小都在1~62之间，其中的字符只为数字或大小写字母。

题解：

很类似之前做过的一道cf的题目，利用shift-and算法优化到nm/64的复杂度

每一次匹配的结果实际上就是(v<<1)&Mask[S[i]]的结果（有点像卷积）

然后一步步左移就可以了。

还有一个比较坑的地方是会卡cin（有些奇怪的字符）

需要用gets和getchar来做。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <bitset>

using namespace std;

const int maxn = ;

typedef long long LL;

int tab[];

char S[maxn], T[];

bitset<> v, Mask[];

int L, n, x;

void pre(){

    memset(tab, , sizeof(tab));

    int tot = ;

    for(int i = 'a'; i <= 'z'; i++) tab[i] = tot++;

    for(int i = 'A'; i <= 'Z'; i++) tab[i] = tot++;

    for(int i = ''; i <= ''; i++) tab[i] = tot++;

}

int main()

{

    pre();

    while(gets(S)){

        L = strlen(S);

        cin>>n;

        for(int i = ; i <= ; i++) Mask[i].reset(); v.reset();

        for(int i = ; i <= n; i++){

            scanf("%d", &x);

            cin>>T;

            for(int j = ; j < x; j++) Mask[tab[T[j]]][i] = ;

        }

        int fail = ;

        v[] = ;

        for(int i = ; i < L; i++){

            if(S[i] <  && tab[S[i]] < ) v = (v<<)&Mask[tab[S[i]]]; else v.reset();

            v[] = ;

            if(v[n] == ){

                fail = ;

                printf("%d\n", i-n+);

            }

        }

        if(fail) printf("NULL\n");

        getchar();

    }

    return ;

}