KMP——字符串匹配
声明
本文主要是一些代码，加一些例题，基本为模板，仔细内容讲解会给出其他博主的链接
如果想要知道一个字符串是否在另一个字符串中出现过，那么首先想到的就是暴力枚举
#include
#include
#include
#include
#include
using namespace std;
string s1,s2;
int baolipipei() {
int len1=s1.size() ;
int len2=s2.size() ;
int i=0,j=0;
while(i>s1>>s2;
cout< 但是，在两个字符串都很长的情况下，时间复杂度就很大，因此，给出一种算法KMP，可以解决字符串匹配等一类问题，在说KMP之前呢，首先说一下KMP用的一个数组，next数组（名字先不要在意）。next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
那么如何求这个数组呢，暴力可以，但是复杂度过大
里面有详细的讲解，各位可以参考一下，主要还是理解之后大家记模板，也比较好记
https://blog.csdn.net/buppt/article/details/78531384
下面给出代码：
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1005;
string s;
int next[maxn];
//最长前后缀相等
void GetNext() {
int i,j=-1;
next[0]=-1;
//初始化为j=-1,next[0]=-1
for(int i=1;
i>s;
GetNext();
for(int i=0;
i 现在呢开始进行匹配，我们知道，如果用暴力，当匹配到不正确的时候i会回到当前要查找的模式串（pattern）开头在对应的文本串（text）的位置下一位，那么根据next数组的含义，就可以直接回退到离当前j最近的j’使text[i] = pattern[j’+1] 能够成立。
这应该是博客上比较好的讲解kmp算法的了（可以看一看）：
https://blog.csdn.net/v_july_v/article/details/7041827
KMP算法的一般思路：
① 初始化j=-1，表示pattern当前已被匹配的最后位。
②让i遍历文本串text，对每个i，执行③，④来试图匹配text[i]和pattern[j+1]。
③不断令j=next[j],直到j回退到-1，或者text[i] = pattern[j+1] 成立。
④如果text[i] = pattern[j+1] ，令j++。如果j达到pattern模式串的长度-1,说明pattern是text的子串。
代码如下：
#include
#include
#include
#include
using namespace std;
const int maxn=1005;
string s1,s2;
int next[maxn];
void GetNext() {//计算pattern的next数组
int i,j=-1;
next[0]=-1;
for(int i=1;
i>s1>>s2;
if(KMP()) {
cout<<"Yes\n";
}
else cout<<"No\n";
}
看到了求next数组和字符串匹配的代码后，发现他们惊人的相似，事实上：求解next数组的过程就是模式串自己匹配的过程。
接下来，怎么用KMP来统计子串出现的次数呢？
暴力的思路肯定还是回到开头，但是知道了上面的内容，我们回溯肯定就用next[j]了。
代码如下：
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1005;
int next[maxn];
string s1,s2;
void GetNext() {
int j=-1;
next[0]=-1;
for(int i=1;
i>s1>>s2;
cout< next优化：
当next[j]表示的串的j+1位失配时，就要继续进行回退，那么如果还失配，同样的还要回退，我们最开始做next数组的意义不就是减少无用功吗?因此改变了一下next数组存放的内容，让失配时回退一次就行了。那么现在，我们把优化后的next数组几位nextvel数组，他失去了next数组的最长前后缀相等的含义，现可理解为当模式串pattern的i+1位失配时，i应该会退的最佳位置。
代码如下：
#include
#include
#include
#include
using namespace std;
const int maxn=1005;
string s;
int nextvel[maxn];
//nextvel[i]的含义应理解为当模式串的i+1完全失配时，i应当退回的最佳位置 j
void GetNextvel() {
int j=-1;
nextvel[0]=-1;
for(int i=1;
i>s;
for(int i=0;
i nextvel数组可以直接替换掉KMP中的next数组
直接套模板的几道题：
http://poj.org/problem?id=3461
#include
#include
#include
#include
#include
using namespace std;
const int maxn1=1e6+5;
const int maxn2=1e4+5;
char s2[maxn2],s1[maxn1];
int next[maxn2];
int len1,len2;
void GetNext() {
int j=-1;
next[0]=-1;
for(int i=1;
i 【KMP——字符串匹配】http://poj.org/problem?id=2752
这是直接利用next数组的题目，需要的就是最大前后缀，而next数组刚好有这个意思
#include
#include
#include
#include
#include
using namespace std;
const int maxn=400005;
int next[maxn];
int shu[maxn];
char s[maxn];
void GetNext(int len) {//求出每一位前缀后缀最大，用next记录
int j=-1;
next[0]=-1;
for(int i=1;
i=0;
i--){//反向输出
printf("%d",shu[i]);
if(i) printf(" ");
}
printf("\n");
}
}
http://caioj.cn/problem.php?id=1177
#include
#include
#include
#include
#include
#include
#include
#include 最后，其实我个人觉得一些算法模板直接记录下来，能够熟练的打下来也很厉害了（小声说）
推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想（）
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术