【hdu5716】带可选字符的多字符串匹配

  • 本文为博主原创，未经许可不得转载

$shift-and$算法，大致就是设$v[i][j]$表示读到文本串的$s[i-j+1]~s[i]$是否出现在相应集合中，

$f[i][j]$表示第$j$个集合中是否有字符$i$，那么有$$v[i+1][j+1]=v[i][j]且f[s[i+1]][j+1]$$

显然$j$这一维可以用$bitset$加速，时间复杂度$O(\frac{nm}{64})$。

关于此算法，推荐一篇文章：

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 2000010
using namespace std;
typedef bitset<550> Int;
int n,m,CantCount;
char str[MAXN],ch[550];
Int f[105],v;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int get(char ch){
	if(ch>='0'&&ch<='9')  return ch-'0'+1;
	else if(ch>='a'&&ch<='z')  return ch-'a'+11;
	else if(ch>='A'&&ch<='Z')  return ch-'A'+37;
	else return 0;
}
void solve(){
	n=strlen(str+1);  m=read();  CantCount=1;  v.reset();
	for(int i=1;i<=100;++i) f[i].reset();
	for(int i=1;i<=m;++i){
		int len=read(); scanf("%s",ch+1);
		for(int j=1;j<=len;++j)  f[get(ch[j])][i]=1;
	}
	for(int i=1;i<=n;++i){
		v=(v<<1)&f[get(str[i])];  v[1]=f[get(str[i])][1];
		if(v[m])  printf("%d\n",i-m+1),CantCount=0;
	}
	if(CantCount)  puts("NULL");
	getchar();
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(gets(str+1)) solve();
	return 0;
}

本文标题:【hdu5716】带可选字符的多字符串匹配

文章作者:chty

发布时间:2018年03月02日 - 16时55分

最后更新:2018年03月02日 - 17时13分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,