首页 > 代码库 > Regular Number hdu-5972(bitset+Shift-And算法)
Regular Number hdu-5972(bitset+Shift-And算法)
(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.
InputIt 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)ai(1≤ai≤10),representing that the i-th position of regular expression has aiai numbers to be selected.Next there are aiainumeric characters. In the last line,there is a numeric string.The length of the string is not more than 5 * 10^6.OutputOutput all substrings that can be matched by the regular expression. Each substring occupies one lineSample Input
4 3 0 9 7 2 5 7 2 2 5 2 4 5 09755420524
Sample Output
9755 7554 0524
题意:有n组数,同组数之间的关系是 | ,然后输入一行字符串,问字符串有哪些子串能够用这n组数来表示??
Input:
先输入n,然后输入n组数,每组数的第一个(ai)表示这组数的长度,然后输入ai个数,他们之间的关系是 | ,然后输入一行字符串。
Output:
输出满足条件的子串。
思路:开一个规格为10的bitset数组和一个bitset类型的test,然后根据输入存放bitset数组。输入字符串后对字符串进行遍历当test[n]==1时输出字符串[i-n+1,i]。输出是可以把下一个变成‘\0’输出字符串s+i-n+1,然后再变回来。
AC代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <algorithm> 6 #include <map> 7 #include <set> 8 #include <stdlib.h> 9 #include <stack> 10 #include <vector> 11 #include <cmath> 12 #include <bitset> 13 #define ll long long 14 using namespace std; 15 const int maxn=1005; 16 bitset<maxn>vec[10]; 17 bitset<maxn>dp; 18 char s[5000005]; 19 int main() 20 { 21 int n,m,x; 22 while(~scanf("%d",&n)) 23 { 24 for(int i=0;i<=9;i++) 25 vec[i].reset(); 26 for(int i=0;i<n;i++) 27 { 28 scanf("%d",&m); 29 for(int j=0;j<m;j++) 30 { 31 scanf("%d",&x); 32 vec[x].set(i); 33 } 34 } 35 scanf("%s",s); 36 int len=strlen(s); 37 dp.reset(); 38 for(int i=0;i<len;i++) 39 { 40 dp=dp<<1; 41 dp=dp.set(0); 42 dp=dp&vec[s[i]-‘0‘]; 43 if(dp[n-1]==1) 44 { 45 char c=s[i+1]; 46 s[i+1]=‘\0‘; 47 printf("%s\n",s+i-n+1); 48 s[i+1]=c; 49 } 50 } 51 } 52 return 0; 53 }
Regular Number hdu-5972(bitset+Shift-And算法)