kmp算法
程序员文章站
2023-11-13 09:30:52
KMP算法 KMP是一种字符串匹配算法。此算法的核心在于$kmp$数组以及它的求法。 （以下约定字符串下标从$1$开始） $\bm{kmp}$数组 定义$kmp$数组：$kmp_{a,i}$表示字符串$a$的前缀$a_{1\sim i}$的最长相同真前后缀的长度，即$kmp_{a,i}=\max\l ......
kmp算法就是在一个字符串中寻找一个字串的过程。
设主串后面用m表示(长度为m)：a b a c a a b a c a b a c a b a a b b
模式串后面用n表示(长度为n)： a b a c a b
我们可以发现当进行到底6位的时候，与主串不同，现在我们应该去移动模式串，可是应该怎么移动呢？我们在第6位之前去找公共的前后缀，然后把前缀移动到后缀，这样就大大的节约了时间。可是应该怎样把前缀的位置移动到后缀并记录下来呢？用nx数组记录
void getnx()
{
int i=0,j=-1;
nx[0]=-1;
while(i<l1)
{
if(j==-1||s1[i]==s1[j])
{
++i;
++j;
nx[i]=j;
}
else
j=nx[j];
}
}接下来是写kmp算法
假设现在文本串s2匹配到 i 位置，模式串s1匹配到 j 位置
如果j = -1，或者当前字符匹配成功（即s2[i] == s1[j]），都令i++，j++，继续匹配下一个字符；
如果j != -1，且当前字符匹配失败（即s2[i] != s1[j]），则令 i 不变，j = nx[j]。意味着失配时，模式串s1相对于文本串s2向右移动了j - next [j] 位。
int kmp()
{
int i=0,j=0,ans=0;
while(i<l2)
{
if(j==-1||s2[i]==s1[j])
{
++i;
++j;
}
else
j=nx[j];
if(j==l1)
{
ans++;
j=nx[j];
}
}
return ans;
}
本文地址：https://blog.csdn.net/sz0902/article/details/107877172