http://acm.hdu.edu.cn/showproblem.php?pid=5972
Regular Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
(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
Output
Sample Input
3 0 9 7
2 5 7
2 2 5
2 4 5
09755420524
Sample Output
7554
0524
Source
2016ACM/ICPC亚洲区大连站-重现赛(感谢大连海事大学)
题意
思路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<bits/stdc++.h> using namespace std; const int maxn = 5e6 + 5; bitset<1005> b[12]; char s[maxn]; struct FastIO { static const int S = maxn * 2; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if(pos == len) pos = 0, len = fread(buf, 1, S, stdin); if(pos == len) exit(0); return buf[pos ++]; } inline int xint() { int s = 1, c = xchar(), x = 0; while(c <= 32) c = xchar(); if(c == '-') s = -1, c = xchar(); for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline void xstring(char *s) { int c = xchar(); while(c <= 32) c = xchar(); for(; c > 32; c = xchar()) * s++ = c; *s = 0; } inline void wchar(int x) { if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos ++] = x; } ~FastIO() { if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } } io; int main() { int n; while(1) { n = io.xint(); for(int i = 0; i < 10; i++) b[i].reset(); for(int i = 0; i < n; i++) { int x = io.xint(); while(x--) { int y = io.xint(); b[y][i] = 1; } } io.xstring(s); bitset<1005> ans; for(int i = 0; s[i]; i++) { ans <<= 1; ans[0] = 1; ans &= b[s[i] - '0']; if(ans[n - 1]) { for(int j = i - n + 1; j <= i; j++) io.wchar(s[j]); io.wchar('\n'); } } } return 0; } |