首页 > 代码库 > HDU5716 : 带可选字符的多字符串匹配
HDU5716 : 带可选字符的多字符串匹配
shift-and算法，设$v[i][j]$表示文本串长度为$i$的前缀能否匹配模式串长度为$j$的前缀，$f[i][j]$表示字符$i$能否匹配模式串的第$j$个位置，那么有$v[i+1][j+1]=v[i][j]\ and\ f[s[i+1]][j+1]$。
显然$j$这一维可以用bitset加速，时间复杂度$O(\frac{nm}{64})$。
#include<cstdio>#include<bitset>int n,i,j,flag;std::bitset<505>v,f[62];char s[2000010],t[99];inline int id(char x){ if(x>=‘a‘&&x<=‘z‘)return x-‘a‘; if(x>=‘A‘&&x<=‘Z‘)return x-‘A‘+26; if(x>=‘0‘&&x<=‘9‘)return x-‘0‘+52; return -1;}int main(){ while(gets(s)){ scanf("%d",&n); for(flag=0,i=0;i<62;i++)f[i].reset();v.reset(); for(i=1;i<=n;i++){ scanf("%d%s",&j,t); for(j=0;t[j];j++)f[id(t[j])][i]=1; } v[0]=1; for(i=0;s[i];i++){ if(id(s[i])<0)v.reset();else v=v<<1&f[id(s[i])]; v[0]=1; if(v[n]==1)flag=1,printf("%d\n",i-n+2); } if(!flag)puts("NULL"); getchar(); } return 0;}HDU5716 : 带可选字符的多字符串匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。