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位的，注意一下。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #include<bitset>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 bitset<N> p[], ans;

 char s[];

 int n;

 void solve() {

     for (int i=; i<; ++i) p[i].reset();

     for (int i=; i<n; ++i) {

         for (int x=read(), y; x--; ) y = read(), p[y].set(i);

     }

     scanf("%s", s + );

     int len = strlen(s + );

     ans.reset();

     for (int i=; i<=len; ++i) {

         ans <<= ;

         ans.set();

         ans &= p[s[i] - ''];

         if (ans[n - ] == ) {

             char c = s[i + ];

             s[i + ] = '\0';

             puts(s + i - n + );

             s[i + ] = c;

         }

     }

 }

 int main() {

     while (~scanf("%d", &n)) solve();

     return ;

 }