题意:
给一个长度为n的模式子串,子串的每个位置分别可以是一些数字,即一个位置可以被多个数字匹配。再给定一个母串,问子串可以在哪些位置和木串匹配,并且输出匹配成功后的所有子串。
解题方法:
对于每一个数字建立一个bitset,然后对于每个bitset b[i]的数字来说, 如果允许它出现在字串j的位置,就让b[i][j] = 1。维护一个bitset ans,枚举母串的每一个位置i,先将ans向高位移一位,再将ans的最低位置1后与这个位置的数字对应的bitset相与。这样,如果ans[k]=1表示从这个位置开始往前的长度为k+1的串可以和子串的前缀进行匹配。当ans[n-1]的时候,说明从i-n+1位置开始的母串可以和子串匹配,这个时候输出即可。由于巨大的io,所以需要加上FastIO才能通过。
这个思路画个图如下:
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
bitset <1005> b[12];
typedef long long LL;
struct FastIO
{
static const int S = 2 * N;
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 xuint()
{
int c = xchar(), x = 0;
while (c <= 32) c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
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;
}
inline void wint(LL x)
{
if (x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
while (n--) wchar(s[n]);
}
inline void wstring(const char *s)
{
while (*s) wchar(*s++);
}
~FastIO()
{
if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
char s[N];
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, y;
x = io.xint();
while(x--){
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;
}