学习记录一下kmp算法，本文主要参考一下几篇博客。
https://blog.csdn.net/a1b2c3d4123456/article/details/50506454
https://blog.csdn.net/crazy_scott/article/details/79211961
https://blog.csdn.net/qq_37969433/article/details/82947411
KMP算法本质上是为了解决字符串匹配的问题。首先我们来看暴力的字符串匹配方法。
1. 暴力匹配
从原字符串开始搜索，若出现不能匹配，则从原搜索位置+1继续。时间复杂度O(m*n)。
虽然前4位一样但是第5位不一样，需要从原来的位置+1,再进行匹配。
以此类推，直到匹配为止。
/*
检测从主串strA的pos位置开始，是否有和子串strB匹配,如果有返回匹配开始位置，如果没有，返回-1
strA:主串
strB:子串
pos:主串开始位置
*/
int getIndex(string strA, string strB, int pos){
int lenA=strA.size();
int lenB=strB.size();
int i=pos,j=0;
while(i<lenA && j<lenB){
if(strA[i]==strB[j]){
i++;
j++;
}else{
i = i-j+1;
j=0;
}
}
return j==lenB?i-lenB:-1;
}
2. KMP匹配
KMP算法其实就是一种改进的字符串匹配算法，关键是利用匹配后失败的信息，尽量减少模式串（W）与主串（T）的匹配次数以达到快速匹配的目的。具体实现就是实现一个next() 函数，函数本身包含了模式串的局部匹配信息。时间复杂度 O(m+n)。 KMP算法利用已经部分匹配这个有效信息，保持i指针（主串）不回溯，通过修改j指针，让模式串尽量地移动到有效的位置，具体可见下面一个例子。
-
比如，Wj处失配，绿色的是Wj，则我们可以确定W1…Wj-1是与Ti…Ti+j-2相对应的位置一一相等的;
-
假设W1…Wj-1中，W1…Wk-1与Wj-k+1…Wj-1是一一相等的，为了下面说的清楚，把这种关系叫做“首尾重合”部分（字符串前缀与后缀重复）
-
那么可以推出，W1…Wk-1与Ti…Ti+j-2
-
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j个元素首尾重合部分个数，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值。
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
2.1 Next函数
我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！
#include <vector>
#include <string>
#include <iostream>
using namespace std;
vector<int> kmp_next(string &m){
vector<int> next(m.size(), 0);
next[0]=0;
int temp;
for(int i=1; i<next.size(); i++){
temp=next[i-1];
while(m[i]!=m[temp]&&temp>0) temp=next[temp-1];
if(m[i]==m[temp]) next[i]=temp+1;
else next[i]=0;
}
return next;
}
bool kmp_search(string text,string m,int &pos){
vector<int> next=kmp_next(m);
int tp=0;
int mp=0;
for(tp=0; tp<text.size(); tp++){
while(text[tp]!=m[mp]&&mp) mp=next[mp-1];
if(text[tp]==m[mp]) mp++;
if(mp==m.size()){
pos=tp-mp+1;
return true;
}
}
return false;
}
int main(){
int pos;
if(kmp_search("sdsadabcdef", "abc", pos)) cout << pos << endl;
return 0;
}
