题意:给你N位数,接下来有N行,第i行先输入n,表示这个数的第i 位上可以在接下来的n个数中挑选,然后i 行再输n个数。
然后输入需要匹配的母串,让你输出母串中有多少个可行的N位子串。
n<=1e3,len<=5e6
这题 bitset 的使用相当于是作为一个指针来使用的。
首先用bitset定义出现的数会在哪几位上出现,置为1。
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("\n"); 卡常
48 char tmp=ch[i+1];
49 ch[i+1]='\0';
50 puts(ch+i-n+1);
51 ch[i+1]=tmp;
52 }
53 }
54 }
55 return 0;
56 }
57