部分内容引自皎月半洒花的博客
模式串匹配问题模型
给定一个需要处理的文本串和一个需要在文本串中搜索的模式串,查询在该文本串中,给出的模式串的出现有无、次数、位置等。
算法思想
每次失配之后不会从头开始枚举,而会从最大可能匹配位置开始重新匹配
考虑数据
模式串:abcabc
文本串:abcabdababcabc
匹配过程中文本串的$d$和模式串末位的$c$出现了失配,由目前的匹配结果可知模式串的前五位$abcab$与文本串失配位置前的五位匹配,取模式串中匹配的部分$S$,当且仅当$S$中有任何与后缀相同的前缀,满足该前缀一定与文本串失配位置前的若干位匹配,取满足上述条件的最大前缀与文本串匹配,再尝试重新匹配下一位(这一位置即为最大可能匹配位置),重复该过程直到匹配成功或不存在这样的前缀时结束
模式串: abcabc
文本串:abcabdababcabc
$next$数组
$next[i]$表示前$i-1$位(从第0位开始)匹配而第$i$位失配时应跳转到的位置,该位置满足前$next[i]-1$位仍与文本串匹配
$next$数组的处理
自匹配,使模式串与自身进行匹配,匹配过程中处理出下一位的$next$值,即当前位的最大匹配的后一位
代码
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=1e6+10; char s[maxn],st[maxn]; int n,m,nxt[maxn]; void getnext() //自匹配(next数组的处理) { for(int j=0,i=1;i<m;i++) { while(j&&s[i]!=s[j]) j=nxt[j]; nxt[i+1]=(j+=s[i]==s[j]); //若i,j位置匹配成功,显然s[1~j]是s[1~i]的最大的,满足前后缀相等的前缀,则j+1为s[i]的最大可能匹配位置 //否则j必为0,意为没有任何成功的匹配 } } int main() { scanf("%s%s",st,s); n=strlen(st),m=strlen(s); getnext(); for(int j=0,i=0;i<n;i++) //i为文本串位置,j为模式串当前尝试匹配的位置 { while(j&&st[i]!=s[j]) //重复取最大可能匹配位置,直到匹配成功或不存在任何可能的匹配 j=nxt[j]; if(st[i]==s[j])//若匹配成功,模式串尝试匹配的位置后移一位 if(++j==m) { printf("%d\n",i-j+2); j=nxt[j]; //若匹配成功则统计答案并重置匹配位置 } } for(int i=1;i<=m;i++) printf("%d ",nxt[i]); printf("\n"); return 0; }