KMP算法及c++实现

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人同时独立发现，后取这3人的姓氏命名此算法。

下面先直接给出KMP的算法流程：

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
  - 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。

很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为 k 的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置，即向右移动的位数为：j - next [j]）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。

#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;

void BuildPatchMatchTable(int *partMatchTable, char *findstr)
{
    if(findstr == NULL)
        return;
    partMatchTable[0] = 0;
    int sizefind = strlen(findstr);
    for(int i = 1; i < sizefind; ++i)
    {
        set<string> preset;
        string tmppre = "";
        tmppre = findstr[0];
        preset.insert(tmppre);
        for(int j = 1; j < i; ++j)
        {
            tmppre = tmppre + findstr[j];
            preset.insert(tmppre);
        }

        set<string> postset;
        string tmppost = "";
        tmppost = findstr[i];
        postset.insert(tmppost);
        for(int j = i - 1; j > 0; --j)
        {
            tmppost =  findstr[j] + tmppost;
            postset.insert(tmppost);
        }
        set<string> comset;
        for(set<string>::iterator beg = preset.begin(); beg != preset.end(); ++beg)
        {
            if(postset.count(*beg) > 0)
                comset.insert(*beg);
        }
        int maxlen = 0;
        for(set<string>::iterator beg = comset.begin(); beg != comset.end(); ++beg)
        {
            if((*beg).size() > maxlen)
                maxlen = (*beg).size();
        }
        partMatchTable[i] = maxlen;
    }
}    

int kmp(char *srcstr, char *findstr)
{
    if(srcstr == NULL || findstr == NULL)
        return -1;
    int lensrc = strlen(srcstr);
    int lenfind = strlen(findstr);
    int *partMatchTable = new int[lenfind];
    BuildPatchMatchTable(partMatchTable, findstr);
    for(int i = 0; i < lenfind; ++i)
        cout << findstr[i] << "\t" << partMatchTable[i] << endl;
    int curFind = 0;
    for(int i = 0; i < lensrc; )
    {
        if(findstr[curFind] == srcstr[i])
        {
            ++i;
            ++curFind;
        }
        else
        {
            if(curFind == 0)
                ++i;
            else
            {
                int movestep = curFind - partMatchTable[curFind-1];
                i += movestep;
                curFind = 0;
            }
        }
        if(curFind == lenfind)
        {
            delete []partMatchTable;
            return i - lenfind;
        }
    }
    return -1;
    delete []partMatchTable;
}
 

int _tmain(int argc, _TCHAR* argv[])
{
    char srcStr[] = "bbc abcdab abcdabcdabde";
    char findStr[] = "abcdabd";
    cout << "pos:" << kmp(srcStr, findStr) << endl;

    char srcStr2[] = "bbc abcdab abcdabcdabdezzz";
    char findStr2[] = "zzz";
    cout << "pos:" << kmp(srcStr2, findStr2) << endl;

    char srcStr3[] = "bbc abcdab abcdabcdabde";
    char findStr3[] = "zzz";
    cout << "pos:" << kmp(srcStr3, findStr3) << endl;
    system("pause");
    return 0;
}

参考：从头到尾彻底理解KMP

秒客网

KMP算法及c++实现

相关文章