HDU 5972 Regular Number

Regular Number

http://acm.hdu.edu.cn/showproblem.php?pid=5972

题意：

　　给定一个字符串，求多少子串满足，子串的第i位，只能是给定的数（小于等于9）。

分析：

　　Shift_and算法。bitset优化。

　　bitset<N>p[26]：p[c]表示字符c在子串出现的位置的集合。

　　bitset<N>ans：ans[i]表示能否匹配到i位。

　　在扫一遍母串的过程中，每扫到一位，ans=(ans<<1)|1，表示试图增加一位，这一位的字符是s[i]。但是增加一位可能会造成不匹配的，我们需要找出加上s[i]依然匹配的。假设ans以前在第j位有一个1，说明可以匹配j位了，现在这一位到了j+1，试图匹配一位，使长度变成j+1，那么如果s[i]可以作为第j+1位出现在子串中（就是看子串下一位是不是s[i]），说明可以。所以ans&=p[s[i]]就好了。每扫完一位，看一下ans[n]是否是1。

　　操作的时候，bitset有0位的，注意一下。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #include<bitset>
12 #define fi(s) freopen(s,"r",stdin);
13 #define fo(s) freopen(s,"w",stdout);
14 using namespace std;
15 typedef long long LL;
16 
17 inline int read() {
18     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
19     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
20 }
21 
22 const int N = 1001;
23 
24 bitset<N> p[11], ans;
25 char s[5000005];
26 int n;
27 
28 void solve() {
29     for (int i=0; i<10; ++i) p[i].reset();
30     for (int i=0; i<n; ++i) {
31         for (int x=read(), y; x--; ) y = read(), p[y].set(i);
32     }
33     scanf("%s", s + 1);
34     int len = strlen(s + 1);
35     ans.reset();
36     for (int i=1; i<=len; ++i) {
37         ans <<= 1;
38         ans.set(0);
39         ans &= p[s[i] - '0'];
40         if (ans[n - 1] == 1) {
41             char c = s[i + 1];
42             s[i + 1] = '';
43             puts(s + i - n + 1);
44             s[i + 1] = c;
45         }
46     }
47 }
48 int main() { 
49     while (~scanf("%d", &n)) solve();
50     return 0;
51 }