KMP算法

• 0. 概述
• 1. 求解next数组
• 2. 求解匹配位置的核心函数
• 3. 完整代码

0. 概述

• 在做模式串与文本串的匹配问题时，匹配失败时，如果每次都只向后递进一位，时间复杂度为 $O(n+m)$，很容易被卡成 $O(m×n)$ ，所以为了降低字符串匹配算法的时间复杂度，对模式串中的每一位，设置唯一的特定变化位置，这个在失配之后的特定变化位置可以帮助我们利用已有的数据不用从头匹配，从而节约时间
• 如果主串已匹配相等的前缀序列中有某个后缀恰等于模式串的前缀，那么可以直接将模式串向后滑动到与这些相等字符对其的位置，用 $ne$ 数组记录到它为止的模式串前缀的真前缀和真后缀最大相同的位置
• 当 $i=1$ 或 $i=2$ 时，$ne[i]$ 的返回值是 $1$，即 $ne[1]=ne[2]=1$ (当下标从 $1$ 开始)，因为当 $n=1$ 时（只有一个元素，此时无前后缀），当 $n=2$ 时（两个元素，一个是前缀一个是后缀，仍然回溯到第一个位置）

1. 求解next数组

// 求next数组的过程[s1与自己匹配,通过前后缀来更新ne数组]
for(int i=2,j=0;i<=len1;i++)
{
    while (j && s1[i]!=s1[j+1])
        j=ne[j]; // 如果不匹配的话,j就一直后退
    if(s1[i]==s1[j+1])
        j++; // 如果当前匹配成功的,j向前递推一位
    ne[i]=j; // 记录并且更新当前j的长度
}

• 当看不懂或者忘了的时候建议自己调试模拟跟踪一遍

• 因为 $ne$ 数组是全局初始化，$while()$ 语句中的 $j$ 保证了 $ne[1]=ne[2]$

• 注意next数组的值是根据模式串的前缀和后缀的最大相同位置来的，所以匹配自己。

2. 求解匹配位置的核心函数

// 求匹配的过程[i遍历文本串]
for(int i=1,j=0;i<=len2;i++ )
{
    // 如果不匹配的话,j回退
    while(j && s2[i]!=s1[j+1])
        j=ne[j];
    // 如果相等的话,j向前递推一位
    if(s2[i]==s1[j+1])
        j++;
    // 刚好长度相等的话说明匹配上了,把下标打印出来
    if(j==len1)
    {
        // 文本串的位置减去长度即为下标,加1得到位置
        printf("%d ",i-len1+1);
        // 模板串在模式串中出现的位置可能是重叠的
        // 需要让j回退到一定位置,再让i加1继续进行比较
        // 回退到ne[j]可以保证j最大,即已经成功匹配的部分最长
        j=ne[j];
    }
}

• 核心实现和求解 $next$ 数组的函数差不多，主要是是模式串和文本串之间的匹配，当 $j==len1$ 的时候说明大小相等即匹配上了，这个时候把相应的下标位置输出出来，同时 $j$ 还是要回溯，因为怕遇到位置重叠的情况。

3. 完整代码

题目链接：P3375 【模板】KMP - 洛谷

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int len1,len2; // n是模板串长度,m是文本串
int ne[N]; // next[i] 就是使子串 s2[0···i] 有最长相等前后缀的前缀的最后一位的下标
char s1[N],s2[N]; // s1[]存储模式串,s2[]存储文本串
// 计算p[]在s[]中出现的位置
// ne代表next数组,因为next在C++中是关键字
int main()
{
	cin>>s1+1>>s2+1; // 先输入模式串,再输入文本串[从下标1开始]
	len1=strlen(s1+1);
	len2=strlen(s2+1);
	cout<<len1<<' '<<len2<<endl;
	// 求next数组的过程[s1与自己匹配,通过前后缀来更新ne数组]
	for(int i=2,j=0;i<=len1;i++)
	{
		while (j && s1[i]!=s1[j+1])
			j=ne[j]; // 如果不匹配的话,j就一直后退
		if(s1[i]==s1[j+1])
			j++; // 如果当前匹配成功的,j向前递推一位
		ne[i]=j; // 记录并且更新当前j的长度
	}
	// 求匹配的过程[i遍历文本串]
	for(int i=1,j=0;i<=len2;i++ )
	{
		// 如果不匹配的话,j回退
		while(j && s2[i]!=s1[j+1])
			j=ne[j];
		// 如果相等的话,j向前递推一位
		if(s2[i]==s1[j+1])
			j++;
		// 刚好长度相等的话说明匹配上了,把下标打印出来
		if(j==len1)
		{
			// 文本串的位置减去长度即为下标
			printf("%d ",i-len1);
			// 模板串在模式串中出现的位置可能是重叠的
			// 需要让j回退到一定位置,再让i加1继续进行比较
			// 回退到ne[j]可以保证 j 最大,即已经成功匹配的部分最长
			j=ne[j];
		}
	}
	// 还需要把next数组输出出来
	for(auto num:ne) 
		cout<<num<<' ';
	cout<<endl;
	return 0;
}

打赏