# hdu 5972-Regular Number(字符串匹配)优良自学吧提供hdu 5972-Regular Number(字符串匹配),hdu 5972---Regular Number(字符串匹配)题目链接   Problem Description Using regular expression to define a numeric st

hdu 5972---Regular Number(字符串匹配)

Problem Description
Using regular expression to define a numeric string is a very common thing. Generally, use the shape as follows:
(0|9|7) (5|6) (2) (4|5)
Above regular expression matches 4 digits:The first is one of 0,9 and 7. The second is one of 5 and 6. The third is 2. And the fourth is one of 4 and 5. The above regular expression can be successfully matched to 0525, but it cannot be matched to 9634.
Now,giving you a regular expression like the above formula,and a long string of numbers,please find out all the substrings of this long string that can be matched to the regular expression.

Input
It contains a set of test data.The first line is a positive integer N (1 ≤ N ≤ 1000),on behalf of the regular representation of the N bit string.In the next N lines,the first integer of the i-th line is

Output
Output all substrings that can be matched by the regular expression. Each substring occupies one line

Sample Input
4
3 0 9 7
2 5 7
2 2 5
2 4 5
09755420524

Sample Output
9755
7554
0524

Source
2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
typedef long long LL;
const int M=5*1e6+5;
bitset<1005>b[12];
bitset<1005>ans;
char s[5000005];

int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
for(int i=0;i<10;i++) b[i].reset();
for(int i=0;i<N;i++)
{
int n;
scanf("%d",&n);
for(int j=1;j<=n;j++)
{
int k;
scanf("%d",&k);
b[k].set(i);
}
}
getchar();
gets(s);
ans.reset();
int len=strlen(s);
for(int i=0;i<len;i++)
{
ans=ans<<1;
ans.set(0);
ans=ans&b[s[i]-'0'];
if(ans[N-1]==1){
char c=s[i+1];
s[i+1]='\0';
puts(s+i-N+1);
s[i+1]=c;
}
}
}
return 0;
}

（本文来自互联网，不代表搜站(http://www.ylzx8.cn/)的观点和立场）