KMP字符串匹配方法的理解与实现

1.KMP算法理解

1.1

此方法是一种常用的提高字符串匹配效率的算法，由作者Knuth–Morris–Pratt得名。但实际意义是字符串匹配过程中，省略不必要操作的一种方法。
最基础的方法是令匹配模板pattern，从待匹配string的头开始，逐位后移进行操作。如下：

基于KMP算法的匹配方法如下：

如上所示，KMP只用了3次基于pattern的匹配方法就完成了对string的匹配操作，就是这么滴有效率，所以很有必要搞明白！！~_~   

1.2

要完成如上的kmp操作，首先我们要获得一个数组，她记录着此次pattern匹配完成或匹配失败该向后移动多少个单位，然后再重新开始匹配。
这个数组的计算就是KMP的核心内容：

首先：

我们要明白，为什么上述的KMP操作的第二次匹配是直接后移了2个单位后进行的。因为这些数据信息我们从pattern本身就能获得，你看pattern是"abab"，第一次匹配时到第二个a的时候因匹配失败结束，但从"abab"我们可以知道，下一次匹配我们可以直接从string中对应pattern中第二个a的位置开始。因为能匹配到第二个a说明pattern的a前面的部分全部匹配成功，而a后面是b所以向后移动一个单位进行匹配的操作就没有必要了，因为已知后面是b，而开始元素是a，明明知道不能匹配还去操作，这不是傻吗...

接下来：

我们要总结一下上述这种思想的特点，使她能够实现在我们的程序中，让计算机也知道有这么一回事儿。要知道需要向后移动多少单位，我们首先要知道两个数据，一个是我们目前已经匹配的长度，另一个关键数据就是“基于目前已经匹配的字符串的那个：即是自身真后缀又是自身最长前缀的子串”的长度。这句话有点绕啊，不过算法的关键就在这句上了.....下面针对这句比较绕的定义，举个栗子：
例如，pattern 是 'ABCABDFG'
'ABCABDFG' 绿色的是目前匹配到的位置，那么ABCA的“即是自身真后缀又是自身最长前缀的子串”就是A       需要向后移动的单位h = 4 - 1， 3个
'ABCABDFG' 绿色的是目前匹配到的位置，那么ABCAB的“即是自身真后缀又是自身最长前缀的子串”就是AB  需要向后移动的单位h = 5 - 2 ，3个

最后：

我们就可以把这个对应匹配进度应该向后移动多少单位的记录存储到一个数组中，这可谓是一件好装备，然后应用到我们的匹配团战中，发挥她的威力！！

2.上述数组的计算流程

k:记录上次的“即是自身真后缀又是自身最长前缀的子串”的长度
m:记录当前匹配字符个数
ARR:记录移动单位数据的数组
P:pattern字符串
过程如下：
k = 0;
ARR[0]=1;
m = 2;
curr_char =P[m-1]; //当前个数比数组下标大1，下标从0开始
while(curr_char!='\0')
{
        if(P[k] == curr_char)
            k += 1;
        else
            k = 0;
        ARR[m-1] = m - k;
        m += 1;
        curr_char = P[m-1];
}

3.C++代码实现

kmp.cpp

/*****************************
filename: kmp.cpp
description: realize the kmp match algorithm
author: warrior mail:[e-mail]
date:2016-3-12
log:
*****************************/

/****** include *******/
#include "kmp.h"
using namespace std;
/****** define *********/
/****** variable ********/
/****** function *******/
/****************
description: get the max prefix of any index of pattern
input:
    string str_pattern
    int * prefixRecord
output:
    none
****************/
void MaxPrefix(char * str_pattern, int * prefixRecord)
{
    int lastPrefixRecord = 0; //k
    int currentIndex = 0; //m
    char curr_char = 'a';
    if((str_pattern==NULL)|(prefixRecord==NULL))
    {
        cout<<"input error!!"<<endl;
        return ;
    }
    lastPrefixRecord = 0;
    prefixRecord[0]=1;
    currentIndex = 2;
    curr_char = str_pattern[currentIndex-1];
    while(curr_char!='\0')
    {
        if(str_pattern[lastPrefixRecord]==curr_char)
            lastPrefixRecord += 1;
        else
            lastPrefixRecord = 0;

        prefixRecord[currentIndex-1] = currentIndex - lastPrefixRecord;
        currentIndex += 1;
        curr_char = str_pattern[currentIndex-1];
    }
}

kmp.h

#ifndef _KMP_H_
#define _KMP_H_
/****** include *******/
#include <iostream>
#include <stdio.h>
#include <string>
/****** define *********/
/****** variable ********/
/****** function *******/
void MaxPrefix(char * str_pattern, int * prefixRecord);

#endif // _KMP_H_

main.cpp

#include "kmp.h"
#include <string.h>
using namespace std;

int main()
{

    string str_1("abcdabcabcdaef");
    char *str_2 = new char[str_1.length()];
    strcpy(str_2, str_1.c_str());
    int* preARR = new int[str_1.length()];
    MaxPrefix(str_2, preARR);
    for(int i=0 ;i<str_1.length(); i++)
    {
        cout<<"  "<<preARR[i];
    }
    cout<<endl;
    delete str_2;
    return 0;
}

4.总结

参考链接：
http://blog.sina.com.cn/s/blog_6cf48afb0100n561.html
%E2%80%93Morris%E2%80%93Pratt_algorithm



.