2016ACM/ICPC亚洲区大连站-重现赛 B

题目如下

给你一个长度为 n 的字串，之后 n 行每行输入 a 然后输入 a 个 ai 代表 字串的第 i 位可以为 a0-----aa。

最后输入主串，问主串中包含了多少个可行的字串，输出字串。

字符串判断题。。开始想用 kmp 但是发现 没有重复性的话就会超时。。

所以这道题用了一个 bitset 来优化一种 shift_and 算法。。

首先我们了解一下 bitset 这种东西你可以理解成一个空间优化过的 bool 数组来表示一个数字的二进制数。

以下为 bitset 学习博客：https://www.cnblogs.com/RabbitHu/p/bitset.html 里边讲的很清楚。

那么问题来了。。这道题可以采用一种空间压缩的思想。

第 i 位的数字可以为 j ，那么我们不妨开 10个 bitset 来记录数字 0-9可以出现的位置

然后再开一个 ans 作为模板串，每次 对这个模板串的末位 赋值 1 然后判断完后就左移1位。

比如 第一位我判断完成了， 成功匹配了 那么这个 1移动到了第二位，我们再去判断时（判断我们采取 ans & num [ i ] 来处理）

如果第二位还可以出现，那么这个 1 还会继续向左移动下去，知道判断到 第 n 位，如果还可以成立，那么我们就可以知道这个

字串是符合的。。当然这么说可能有一些抽象

举个例子 假设 字串只有 3 为 只允许字串为 123

那么对于 Bitset 来讲

num[1] = 001    num[2] = 010     num[3] = 100

主串 为 ：  122212321323

我们去模拟这个算法做一下。。就会更加深理解。。。

看来还是太弱了。。。还需要掌握更多的算法。。。这次终于了解了 bitset 是什麽。。也了解了一下 shift_and　算法。。有一些收获吧。

以下为　ＡＣ　代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
using namespace std;
int n;
const int maxn = 5e6+5;
bitset<1005> num[12];
bitset<1005> ans;
char s[maxn];
int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<10;i++)
num[i].reset();
for(int i=0;i<n;i++)
{
int t;
scanf("%d",&t);
while(t--)
{
int k;
scanf("%d",&k);
num[k].set(i);
}
}
scanf("%s",s);
ans.reset();
int len=strlen(s);
for(int i=0;i<len;i++)
{
ans = ans<<1;
ans.set(0);
ans=ans&num[s[i]-'0'];
if(ans[n-1])
{
char c=s[i+1];
s[i+1]='';
puts(s+i-n+1);
s[i+1]=c;
}
}
}
return 0;
}

最后

以上就是孤独鸵鸟为你收集整理的2016ACM/ICPC亚洲区大连站-重现赛 B的全部内容，希望文章能够帮你解决2016ACM/ICPC亚洲区大连站-重现赛 B所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。