首页 > 代码库 > hdu 5972---Regular Number(字符串匹配)
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.
(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
Source
2016ACM/ICPC亚洲区大连站-重现赛(感谢大连海事大学)
题意:输入N ,表示有一个长为N的子串,接下来N行,每行输入ai 和ai个数,表示有ai个数,表示子串第i个字符为ai个数中的一个,也就是这个子串的正则式,然后输入一个主串,要求输出这个主串中包含的所有的子串。
思路:使用bitset<N> b[10] ,b[i][j]表示值为i的数可以出现在子串的那些位置,即下标,那么对主串进行遍历 i=0:len-1 。另外定义一个变量bitset<N> ans ,每次先将ans左移一位,然后将最低位置1,然后令k=当前输入的数,将ans=ans&b[k], 如果当前ans[N-1]==1,那么主串s[i-N+1]~s[i]就是合法子串,输出;
代码如下:
#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;}
hdu 5972---Regular Number(字符串匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。