【C++】KMP算法详解
KMP算法简介：KMP算法是一种高效的字符串匹配算法，关于字符串匹配最简单的就是BF算法。BF算法是用两个游标分别指向母串S，模式串T，从开头向后面依次比较字符是否相等，如果相等继续同时向后滑动两个游标，不相等的话，T的游标回溯至开头，S的游标回溯至起初游标的下一位，这种算法原理非常简单，小学生都可以想的到。
KMP算法是在BF算法的基础上加以改进的，它的特点是在遇到字符不匹配时候维持母串T的游标不动，而把模式串向右移动，具体移动到哪一个元素下标，这就是算法的核心思想之处了。
假如母串的i处和模式串的j处不匹配，那么就令k=next（j），表示的意思就是：模式串在j处出现不匹配现象，此时应该将模式串向后一定到下标为k的游标处，在此与之前不匹配的元素进行比较。
Kmp算法的本质：
如图所示：
在下标j处出现不匹配，则k = next（j），表示此时应该把下标k移动到原本j对应的位置处，用T跟s进行对比。如果满足这样的条件，则有T,T,…T = S,S,…S
又因为j之前的字符串跟S都匹配，所以又有T,T,…T = S,S,…S.所以得出T,T,…T = T,T,…T。也就是说图中被标记出来前后两个区域的字符串相等，KMP算法的本质就是找出最大的这样一个k值满足T,T,…T = T,T,…T。
K值的求取方法：
K值的求取用到了数学中的递推的思想，求取K值只跟模式串T自身有关，跟母串S半毛钱关系都没有。先假设已经有 next(j) = k,接下来我们就去求next（j+1）的值。这个要分情况讨论:
如果T = T那么就很容易得到 next(j+1) = k+1 = next(j) + 1;
如果T != T，那么此时可以将T,T,…T,T看做一个模式串，T,T,…T,T看做一个母串，此时模式串在k处出现不匹配现象，那么我们获取next（k）= k1的值，判断T跟T的值是否相等，如果相等那么next(j+1) = k1+1;如果不相等再往下求新的kn的值，直到T = T，或者遍历到了模式串的开头都不想的话，此时就要把i向后移动一个位置，同时用模式串的开头指向i，或者抽象一点就是把模式串开头的前一位下标（-1）指向i。因为下标（-1）是没有意义的，所以此时等效于下标（0）指向母串的i+1。
算法的实现：
这里一共列出了三个版本的kmp算法，其中第一个是本人根据对算法的理解写的，也是最丑的一个，剩下的两个是改编严蔚敏版的《数据结构与算法》一书中的。
Algorithms.h//Algorithms.h
#pragma once
#include <string>
using namespace std;
class Algorithms
{
public:
Algorithms(void);
static int kmp1(string str1,string str2);
static int kmp2(string str1,string str2);
static int kmp3(string str1,string str2);
~Algorithms(void);
};
//Algorithms.cpp
#include "Algorithms.h"
#include <vector>
#include <iostream>
using namespace std;
Algorithms::Algorithms(void)
{
}
Algorithms::~Algorithms(void)
{
}
int Algorithms::kmp1(string strS,string strT)
{
int nSize = strT.size();
vector<int> vecNext(nSize,-1);
if (nSize >= 2)
vecNext =0;
for (int i=2;i<nSize;i++)
{
int k = vecNext;
while (k>=0 && strT != strT )
k = vecNext;
if(k>=0 && strT == strT)
vecNext = k + 1;
else
vecNext = 0;
}
for(int i=0;i<nSize;i++)
cout<<"the vector is:"<<i<<": "<<vecNext<<endl;
int nLength = strS.size();
int nCount = 0;
int nPoss = 0;
int nPost = 0;
while(nPoss < nLength)
{
if ( strS == strT )
{
nPoss++;
nPost++;
}
else
{
nPost = vecNext;
if (nPost == -1)
{
nPoss++;
nPost++;
}
}
if (nPost == nSize )
{
nCount++;
nPost = 0;
}
}
return nCount;
}
int Algorithms::kmp2(string strS,string strT)
{
int nSize = strT.size();
vector<int> vecNext(nSize);
int i = 0;
vecNext = -1;
int j = -1;
while(i<nSize-1)
{
if (j==-1 || strT==strT)
{
i++;
j++;
vecNext = j;
}
else
j = vecNext;
}
for(int i=0;i<nSize;i++)
cout<<"the vector is:"<<i<<": "<<vecNext<<endl;
int nLength = strS.size();
int nCount = 0;
int nPoss = 0;
int nPost = 0;
while(nPoss < nLength)
{
if ( strS == strT )
{
nPoss++;
nPost++;
}
else
{
nPost = vecNext;
if (nPost == -1)
{
nPoss++;
nPost++;
}
}
if (nPost == nSize )
{
nCount++;
nPost = 0;
}
}
return nCount;
}
int Algorithms::kmp3(string strS,string strT)
{
int nSize = strT.size();
vector<int> vecNext(nSize);
int i = 0;
vecNext = -1;
int j = -1;
while(i<nSize-1)
{
if (j==-1 || strT==strT)
{
i++;
j++;
if (strT == strT)
vecNext =vecNext;
else
vecNext = j;
}
else
j = vecNext;
}
for(int i=0;i<nSize;i++)
cout<<"the vector is:"<<i<<": "<<vecNext<<endl;
int nLength = strS.size();
int nCount = 0;
int nPoss = 0;
int nPost = 0;
while(nPoss < nLength)
{
if ( strS == strT )
{
nPoss++;
nPost++;
}
else
{
nPost = vecNext;
if (nPost == -1)
{
nPoss++;
nPost++;
}
}
if (nPost == nSize )
{
nCount++;
nPost = 0;
}
}
return nCount;
}main.cpp//main.cpp
#include <iostream>
#include <string>
#include <vector>
#include "Algorithms.h"
using namespace std;
void main()
{
string str1,str2;
cout<<"please input str1:"<<endl;
cin>>str1;
cout<<"please input str2:"<<endl;
cin>>str2;
//cout<<"the number of substr in str1 is:"<<Algorithms::kmp1(str1,str2)<<endl;
//cout<<"the number of substr in str1 is:"<<Algorithms::kmp2(str1,str2)<<endl;
cout<<"the number of substr in str1 is:"<<Algorithms::kmp3(str1,str2)<<endl;
system("pause");
}算法评析：
1：Kmp1
先说下我自己写的吧，代码没有书上的简洁，再说说几个为什么。为什么循环要从i=2开始？
因为要用到int k = vecNext，以及strT != strT，如果从i=1开始的话，k的起始值=-1，这样就会出现越界的情况，所以就从i=2开始；另外
next（0）=-1，next（1）=0，这都是毫无疑问的东西，所以可以在前两者已知的情况下，向后求解。
2：Kmp2
Kmp2的巧妙之处在于用了while循环，在需要i变化时才变化，否则已知变换j的值（j表示的是next（i））
3：Kmp3
Kmp3是对kmp2的改进，它考虑到了这样的一种情况：首先在T(i) = T(j)的情况下，如果按照kmp2那么next（i+1）= j+1。但是如果T（i+1）=T(j+1)的话，那么此时就无需在拿T(j+1) 跟母串的比较，因为T(i+1)已经比较过了，并且他们不相等，所以不需要再比较T(j+1)只需要令： next（i+1） = next（j+1）。
按照kmp2其实是这样的： next（i+1） = j+1，j+1 = next（j+1），
所以中间省略的一步就是：next（i+1）= j+1。
总结：
关于kmp网上的讲解很多，但是坑爹的错误程序也不少，在验证一个kmp算法程序是否坑爹，只需要把next数组的内容打印出来，将它和自己口算得到的结果比对。百度百科的C++实现的kmp算法就是错误的，坑爹的。
页:
[1]