文章目录
- KMP算法
- 前言
- 1.KMP算法概述
- 2.next数组
- 3.KMP实现
-
- KMP的简单应用：
-
- [J - 剪花布条](https://vjudge.net/problem/HDU-2087)
-
- 题意：
- 思路：
- 来自作者最真诚的吐槽
KMP算法
字符串匹配算法，是在实际工程中经常遇到的问题，也是各大公司笔试面试的常考题目。此算法通常输入为原字符串（string）和子串（pattern），要求返回子串在原字符串中首次出现的位置(做题的时候变化挺多的，基本上没有只返回首次出现的位置，一般都是返回所有的位置，或者出现的次数，还有让你打印出next数组)。比如原字符串为“ABCDEFG”，子串为“DEF”，则算法返回3。常见的算法包括：BF（Brute Force，暴力检索）、RK（Robin-Karp，哈希检索）、KMP（教科书上最常见算法）、BM（Boyer Moore）、Sunday等。今天我来介绍一下KMP算法，以及基本的代码实现和每一步的原理分析……
前言
我觉得KMP算法比较容易理解，你要是认真看了阮大神的KMP文章，基本上就明白他的原理了(懂是懂，但是看不懂算法？！ ……)其实就有两部分比较重要，第一个是next数组的构建，另一个就是如何实现他的字符匹配。(我手推了一下下，发现十行代码之间，KMP灰飞烟灭，属实有点神奇!!!)
1.KMP算法概述
首先还是简单介绍一下KMP与传统的暴力匹配算法的不同点在哪里，难点在哪里。
我们先来看一下暴力的字符串匹配算法
// 暴力匹配（伪码）
int search(String pat, String txt) {
int M = pat.length;
int N = txt.length;
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (pat[j] != txt[i+j])
break;
}
// pat 全都匹配了
if (j == M) return i;
}
// txt 中不存在 pat 子串
return -1;
}
对于暴力算法，如果出现不匹配字符，会同时回退
txt
和
pat
指针，时间复杂度为
O(MN)
,空间复杂度为
O(1)
,最主要的问题是，如果字符串中重复的字符较多，该算法就很蠢。
比如
tex
= ‘’ aaacaaab’’，
pat
= ‘‘aaab’’:
很显然
pat
中跟本没有c，导致在c这里比较了4次，根本没有必要退回指针
i
，暴力算法很明显做了不必要的操作。
KMP优秀就优秀在他花费了一些空间来记录一些信息，来解决上述的情况
比如
txt
= “aaaaaaab”,
pat
= “aaab”,暴力算法会和上面那个例子一样蠢蠢的返回指针i，而kmp算法就会耍小聪明
因为KMP算法知道b字符之前的a都是匹配的，所以每次只需比较b是否被匹配即可
KMP永远不会回退
txt
的指针，就像 我高中晓明老师说的好：不走回头路。（就是不会重复扫描
txt
），而是借助next数组的信息把
pat
移动到正确的位置继续匹配.
这个算法的难点在于如果计算next函数的信息？如何根据这些信息正确的移动
pat
的指针？
所以我们接下来来解决一下next数组
2.next数组
咱们再举个栗子
txt
= “BBC ABCDAB ABCDABCDABDE”
pat
= “ABCDABD”
我们要求的是
pat
的next数组
首先next数组其实是字符串的部分匹配表，由部分搜索词和部分匹配值组成
搜索词就是
pat
的每一个元素
部分匹配值就是前缀和后缀的最长共有元素长度
在这之前，我们要先知道什么是前缀和后缀。
前缀是指除了最后一个字符以外的，一个字符串的全部头部组合；
后缀是指除了第一个字符以外的，一个字符串的全部尾部组合
比如字符串“bread”
前缀：b, br, bre, brea
后缀：read， ead， ad，d
对于
ABCDABD
的部分匹配表如下
- "A"的前缀和后缀都为空集，共有元素的长度为0；
- "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
- "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
- "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
- “ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A”，长度为1；
- “ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB”，长度为2；
- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
看到这里你应该明白什么是next数组了，但是你心中一定有个疑惑，我怎么用代码实现呢？？？
别急，听我慢慢道来
你先观察一下上面那个ABCDABD，你会发现第二个A出现的时候，其匹配值就是1，而他后面的B如果和第一个A后面的字符相等，那他的匹配值就是2，一看，确实是一样的B，所以就变成了2。
其实是这么一个过程：你是从第一个开始求，但是第一个字符只有一个元素，故没有前缀和后缀，就是0，然后你就开始比较第二个，一看，A != B,所以也是0，再看三四，都是0，直到你看到了第五个，第五个的A == 第一个的A ，一看匹配成功，我们就记录第五个数的匹配值是1。再就比较下一个字符，也就是第六个。这个时候细心的同学就会问：哎呀，你怎么就判断了这一个元素就判定他是1，而不去遍历看看他的所有前缀后缀有没有其他的一样的，而且长度还超过1的？其实第i个是在第i- 1 的基础上进行的，如果第i个与前面那个匹配了，就在第i- 1的基础上加1.等你看第6和7个字符就明白了，因为第五个字符与第一个字符匹配了，我们就把第六个字符与第二个字符比较一下，实现了“移动”。这个时候发现第六个和第二个字符是相等的，所以第6个的部分匹配值就在第五个的基础上加1，1 + 1 = 2，就是2.。你写一下想一想，就能明白是什么意思。然后我们在看第七个与第三个比较，一看C != D，匹配失败，就为0.这个时候如果还有第八个元素，那第八是要和第一个重新比较的，因为第七个已经匹配失败，所以他的前缀后缀共有元素最多就是1（当且仅当第八个和第一个匹配成功）。
next构造的代码奉上
int next1[1000005];
void getnext()//打表，构造出next数组(这也太神奇了吧这个法)
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;//当字符串只有一个元素的时候，就没有前缀和后缀，所以直接赋值为0；
while(j < m)//表面上看其实可以换成从j从1到m的for循环的,但实际上你要是手推一波你就会发现这个循环不止进行了m-1次，这就是神奇所在
{
if(k == -1 || ss[j] == ss[k])//这个ss[j] 其实就是到最后一个元素，而ss[k] 其实就是第k个元素，看看这两个想不想等
next1[++j] = ++k;
else
k = next1[k];
/*这个就是用来清值的，因为每次求第j个的时候，如果不匹配，就得清值，有可能求一个next1的值时不止用了一次这个玩意，很神奇*/
}
}
这个是我手推的一遍循环过程（不推不知道，一推才知道其中的奥秘）
3.KMP实现
这个地方就要看如何灵活运用next数组的数据进行跳跃了……
（你可以当做板子背下来）
void kmp()
{
int ans = 0;//用来记录出现几次
int i = 0;//i是用来记录被搜字符串的位置
int j = 0;//j是用来记录要搜的字符串的位置
getnext();
for(int i = 0; i < n; i++)
{
while(j > 0 && s[i] != ss[j])//就在这一步，实现了跳跃!,因为j = next[j],从而在i的地方进行s[i]与ss[j]的新的比较
j = next1[j];
if(s[i] == ss[j])//主要是用来找第一次匹配的位置
j++;
if(j == m)//当找到一次以后就输出这个位置
{
ans ++；//找到一次就直接++，计算次数用
cout<<i - m + 2 <<'\n';//这个地方是输出位置的，不知道的话就直接背过就完事了了，咱也不知道为什么要加2，一遍遍试出来的……
j = next1[j];//再刷新j的值，好找下一个，因为最后一个数的next值肯定为0，所以赋它
}
}
}
下面是一到洛谷的KMP模板题
题意大概是这样的：给你两个字符串s1，s2.
让你按从小到大的顺序输出s2在s1中的位置
在输出一行整数，第i个整数代表s2的长度为i的前缀的最长长度（其实就是让你打印next数组的值）
下面是AC码
#include<bits/stdc++.h>
using namespace std;
int next1[1000005];
string s, ss;
int n, m;
void getnext()
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;
while(j < m)
{
if(k == -1 || ss[j] == ss[k])
next1[++j] = ++k;
else
k = next1[k];
}
}
void kmp()
{
int i = 0;
int j = 0;
getnext();
for(int i = 0; i < n; i++)
{
while(j > 0 && s[i] != ss[j])
j = next1[j];
if(s[i] == ss[j])
j++;
if(j == m)
{
cout<<i - m + 2 <<'\n';
j = next1[j];
}
}
}
int main()
{
cin>>s>>ss;
n = s.size();
m = ss. size();
kmp();
for(int i = 1; i <= m; i++)
{
cout<<next1[i]<<' ';
}
return 0;
}
代码的解释都在上面写了
KMP的简单应用：
J - 剪花布条
题意：
给了两个字符串a，b。让你输出a中有几个完整的b
思路：
可以用KMP算法统计，也可以直接用find函数找，然后找到了就可以把这之前的所有字符删除
#include <bits/stdc++.h>
using namespace std;
int next1[1000005];
string s, ss;
int n, m, ans ;
void getnext()
{
int j, k;
j = 0;
k = -1;
next1[0] = -1;
while(j < m)
{
if(k == -1 || ss[j] == ss[k])
next1[++j] = ++k;
else
k = next1[k];
}
}
int kmp()
{
ans = 0;//用来记录出现几次
int i = 0;//i是用来记录被搜字符串的位置
int j = 0;//j是用来记录要搜的字符串的位置
getnext();
while(i <= n && j <= m)
{
if(j == m)//找到了一次s2，就让ans++
{
ans ++;
j = 0;
continue;
}
if(j == -1 || s[i] == ss[j])//i与j处字符匹配成功
{
i++;
j++;
}
else//匹配不成功就利用next数组来跳跃
j = next1[j];
}
return ans;
}
int main()
{
while(cin>>s)
{
if(s[0] == '#')
break;
else
{
cin>>ss;
n = s.size();
m = ss. size();
cout<<kmp()<<endl;
}
}
return 0;
}
来自作者最真诚的吐槽
之前也学了一遍KMP，但是没静下心来去理解，就当做板子直接套（也不知道为什么，我明明记得我在oj上面做了一个KMP的题，还wa了，清清楚楚的，但是现在就是找不到，难道我活在梦里？？！！），现在真正理解了，才知道他有多神奇多牛。还有那个洛谷的题，千万记得写函数用int时，得加返回值，不然就会RE，淦！（你说这直接用void他不香嘛）我差点到死都不知道哪里错了，还好有ycgg告诉我了。
昨天下午学了个markdown，晚上又学KMP，从六点在集训室，到回宿舍继续干，一直干到了零点多，今天上午可算是在图书馆用markdown语言写出来了这篇KMP算法的博文，属实不容易……
不得不说，typora真滴好用，太喜欢这种简约的风格了，吹爆typora……
（好奇怪啊，我导入到csdn的时候，外部的照片就会丢失，果然得去设置一下typora的图片的存储……）