首页 > 代码库 > HDU 5716 带可选字符的多字符串匹配（ShiftAnd）
HDU 5716 带可选字符的多字符串匹配（ShiftAnd）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5716
【题目大意】
给出一个字符串，找出其中所有的符合特定模式的子串位置，符合特定模式是指，该子串的长度为n，并且第i个字符需要在给定的字符集合Si中
【题解】
这种串与字符集的匹配称为柔性字符串匹配，采用ShiftAnd的匹配方法。
bt[i]表示字符i允许在哪些位置上出现，我们将匹配成功的位置保存在dp中，那么就可以用dp[i]=dp[i-1]<<1&bt[s[i]]来更新答案了
利用滚动数组和bitset可以来优化这样的运算，当一个位置的匹配在更新的过程中没有丢失，即始终在特定模式中直到定长，那么这个位置就是成功匹配位
复杂度为O(nm/64)
【代码】
#include <cstdio>#include <bitset>#include <cstring>using namespace std;const int M=510,N=2000010,L=65,U=256;bitset<M> dp[2],bt[U];int n,m,id[U],cnt,l;char s[N],t[L];void init(){ cnt=0; for(int i=‘0‘;i<=‘9‘;i++)id[i]=++cnt; for(int i=‘A‘;i<=‘Z‘;i++)id[i]=++cnt; for(int i=‘a‘;i<=‘z‘;i++)id[i]=++cnt;}void ShiftAnd(int n,int m){ int cur=1,f=0; dp[0].reset(); dp[0].set(0); for(int i=1;i<=n;i++,cur^=1){ dp[cur]=dp[cur^1]<<1&bt[id[s[i]]]; dp[cur].set(0); if(dp[cur][m])printf("%d\n",i-m+(f=1)); }if(!f)puts("NULL");}int main(){ init(); while(gets(s+1)){ n=strlen(s+1); scanf("%d",&m); for(int i=1;i<=cnt;i++)bt[i].reset(); for(int i=1;i<=m;i++){ scanf("%d %s",&l,t); for(int j=0;j<l;j++)bt[id[t[j]]].set(i); }ShiftAnd(n,m);gets(s); }return 0;}
HDU 5716 带可选字符的多字符串匹配（ShiftAnd）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。