HDU 5716 带可选字符的多字符串匹配 （shift-and）

发表于 |
字数统计: 819字 | 阅读时长 ≈ 4min

带可选字符的多字符串匹配

Problem Description

有一个文本串，它的长度为m(1≤m≤2000000)，现在想找出其中所有的符合特定模式的子串位置。
符合特定模式是指，该子串的长度为n(1≤n≤500)，并且第i个字符需要在给定的字符集合Si中。
因此，描述这一特定模式，共需要S1,S2,…,Sn这n个字符集合。每个集合的大小都在1∼62之间，其中的字符只为数字或大小写字母。

Input

第一行为一个字符串，表示待匹配的文本串。注意文本串中可能含有数字和大小写字母之外的字符。
第二行为一个整数n。
以下n行，分别描述n个字符集合。每行开始是一个1∼62之间的整数，随后有一个空格，接下来有一个字符串表示对应字符集合的内容。整数表示字符集合的大小，因此它也就是字符串的长度。输入保证字符串中的字符只为数字或大小写字母且没有重复。（注：本题有多组测试数据）

Output

每当从某个位置开头的，长度为n的子串符合输入的模式，就输出一行，其中包含一个整数，为它在文本串的起始位置。位置编号从1开始。
如果文本串没有任何位置符合输入模式，则最后输出一个字符串”NULL”，占一行。

Sample Input

aaaabacabcabd
3
3 abc
2 bc
3 abc

Sample Output

4
6
8
9

这应该是一道shift-and的模板题了。
注意到每个位置是一个字符集对shift-and并没有影响，仍然只需要处理出文本串中每个字符在匹配串中出现位置，然后直接shift-and即可。

关于shift-and算法，用了一个数组$F[i][j]$,$F[i][j]$表示匹配串以$j$结尾的前缀是否是文本串以$i$结尾的前缀的后缀，简单来说就是模式串以$j$结尾能否匹配当前位置。

考虑转移，$F[i+1][j+1]=1$当且仅当$F[i][j]=1$&&$S[i+1]=T[j+1]$，令$B[i]$表示字符i在串$T$中出现位置的状压。那么有$F[i+1]=(F[i]<<1|1)$&$B[S[i+1]]$，利用bitset实现，可做到$\frac{mn}{32}$，当匹配串较短时可认为是线性。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<bitset>
#define N 2000005
using namespace std;
char s[N],ss[N];
bitset<501>F,B[63];
int id(char t)
{
	if(t>='0'&&t<='9')return t-47;
	if(t>='A'&&t<='Z')return 11+t-'A';
	if(t>='a'&&t<='z')return 37+t-'a';
	return 0;
}
int main()
{
	int i,j,k,n;char c;bool f;
	while(gets(s+1))
	{
		int l=strlen(s+1);
		F.reset();f=0;
		for(i=0;i<63;i++)B[i].reset();
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d",&k);
			scanf("%s",&ss[1]);
			for(j=1;j<=k;j++)B[id(ss[j])][i]=1;
		}
		for(i=1;i<=l;i++)
		{
			F<<=1;F[1]=1;
			F&=B[id(s[i])];
			if(F[n]==1)printf("%d\n",i-n+1),f=1;
		}
		if(!f)puts("NULL");
		c=getchar();
	}
}