Regular Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 789 Accepted Submission(s): 181
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
ai(1≤ai≤10)
,representing that the i-th position of regular expression has
ai
numbers to be selected.Next there are
ai
numeric characters. In the last line,there is a numeric string.The length of the string is not more than 5 * 10^6.
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
题意：
给你N位数，接下来有N行，第i行先输入n，表示这个数的第i 位上可以在接下来的n个数中挑选，然后i 行再输n个数。
然后输入需要匹配的母串，让你输出母串中有多少个可行的N位子串。
解：
这题首先没法使用KMP，因为在匹配失败后没法返回到准确的位置。
然后在网上向别人学了下代码，才明白这题bitset的巧妙的运用。
关于bitset的用法：http://blog.csdn.net/no2015214099/article/details/72902794
这题 bitset 的使用相当于是作为一个指针来使用的。
首先用bitset定义出现的数会在哪几位上出现，置为1。
定义ans的初始位为1，每一次母串对应位与该位出现的数的bitset进行与比较（表明该位上是否能出现该数）。因为一旦失败则置0，因此如果1出现在ans的第n位上则表明之前的n-1位全部匹配成功。
此题，使用bitset的复杂度为O(n*len/x)（len为母串长，x为机器码长）。
此题必须使用puts，gets进行输入输出，不然会超时。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <bitset>
using namespace std;
const int maxn=1e6+50;
char str[5*maxn];
bitset<1005> s[20];
bitset<1005> ans;
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=0;i<20;i++)
s[i].reset();
ans.reset();
for(int i=0;i<n;i++)
{
int N,temp;
scanf("%d",&N);
for(int j=0;j<N;j++)
{
scanf("%d",&temp);
s[temp].set(i);
}
}
getchar();
gets(str);
int len=strlen(str);
for(int i=0;i<len;i++)
{
ans=ans<<1;
ans[0]=1;
ans&=s[str[i]-'0'];
if(ans[n-1]==1)
{
char temp=str[i+1];
str[i+1]='\0';
puts(str+i-n+1);
str[i+1]=temp;
}
}
}
return 0;
}
