題目鏈接 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) ...
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 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; }
