【HDOJ5972】Regular Number（Bitset，ShiftAnd）

题意：给你N位数，接下来有N行，第i行先输入n，表示这个数的第i 位上可以在接下来的n个数中挑选，然后i 行再输n个数。

然后输入需要匹配的母串，让你输出母串中有多少个可行的N位子串。

n<=1e3,len<=5e6

思路：From https://blog.csdn.net/no2015214099/article/details/72902820

这题 bitset 的使用相当于是作为一个指针来使用的。

首先用bitset定义出现的数会在哪几位上出现，置为1。

定义ans的初始位为1，每一次母串对应位与该位出现的数的bitset进行与比较（表明该位上是否能出现该数）。因为一旦失败则置0，因此如果1出现在ans的第n位上则表明之前的n-1位全部匹配成功。

此题，使用bitset的复杂度为O(n*len/x)（len为母串长，x为机器码长）。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<bitset>
 7 typedef long long ll;
 8 using namespace std;
 9 #define N   110000
10 #define oo  10000000
11 #define MOD 1000000007
12 
13 char ch[5100000];
14 bitset<1100> s[10];
15 bitset<1100> ans;
16 
17 int main()
18 { 
19     int n;
20     while(scanf("%d",&n)!=EOF)
21     {
22         for(int i=0;i<10;i++) s[i].reset(); 
23         ans.reset();
24         for(int i=0;i<n;i++)
25         {
26             int x;
27             scanf("%d",&x);
28             for(int j=0;j<x;j++)
29             {
30                 int y;
31                 scanf("%d",&y);
32                 s[y].set(i);
33             }
34         }    
35         //scanf("%s",ch); 卡常 
36         getchar();
37         gets(ch);
38         int len=strlen(ch);
39         for(int i=0;i<len;i++)
40         {
41             ans<<=1;
42             ans[0]=1;
43             ans&=s[ch[i]-'0'];
44             if(ans[n-1]==1)
45             {
46                 //for(int j=i-n+1;j<=i;j++) printf("%c",ch[j]);
47                 //printf("
");  卡常 
48                 char tmp=ch[i+1];
49                 ch[i+1]='';
50                 puts(ch+i-n+1);
51                 ch[i+1]=tmp;
52             }
53         }
54     }
55     return 0;
56 }
57