KMP算法简介

说到字符串匹配，脑袋里自然而然的冒出来KMP，哎，当年还是专门找了好久的材料，最终算是懂点皮毛，在这里跟大家分享一下。
最初的字符串匹配算法都是从头开始，逐个匹配过去，奈何效率不高，最后就是那些“懒”而聪明的大神们，想出了这个算法，供人们使用，在这里先定义一下参与字符串匹配的两个参数：模式字符串，以及目标字符串；我们可以理解为在目标字符串中找出模式字符串~~~
KMP算法就是充分利用模式串的自身信息求出一个巨有用的数组next来进行后续的匹配工作。计算next数组代码如下：

    int patternLen = patternStr.size();
    int targetLen = targetStr.size();
    //next数组一定要记得开大一点
    int next[10005] = { -1 };
    //计算next数组。 ps: next 数组含义--当前位置i失配时， 模式串的指针应该回溯到的位置即next[i]
    //j表示前缀，i表示后缀
    int j = -1, i = 0;
    next[0] = -1;
    while (i < patternLen)
    {
        if (j == -1 || patternStr[i] == patternStr[j])
        {

            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

之后匹配模式串和目标字符串的过程和上面的代码比较类似，如下：

//在目标串中寻找模式串的个数, i表示 目标串的下标，j表示模式串的下标
i = j = 0;
int count = 0;
while (i < targetLen)
{
    if (j == -1)
    {
        i++;
        j++;
    }
    if (patternStr[j] == targetStr[i])
    {
        //当完全匹配时，计数+1，但是为了找下一个完全匹配串，假设最后一个没有匹配，进入下一次循环
        if (j == (patternLen - 1))
        {
            count++;
            j = next[j];
        }
        else
        {
            j++;
            i++;
        }
    }
    else
    {
        j = next[j];
    }
}

下面是全部代码：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string targetStr;
    string patternStr;
    int N;
    cin >> N;
    int n = 0;
    while (n < N)
    {
        cin >> patternStr >> targetStr;
        int patternLen = patternStr.size();
        int targetLen = targetStr.size();
        //next数组一定要记得开大一点，老子可是调了好几天的，可恶的边界条件。。。。
        int next[10005] = { -1 };
        //计算next数组。 ps: next 数组含义--当前位置i失配时， 模式串的指针应该回溯到的位置即next[i]
        //j表示前缀，i表示后缀
        int j = -1, i = 0;
        next[0] = -1;
        while (i < patternLen)
        {
            if (j == -1 || patternStr[i] == patternStr[j])
            {

                i++;
                j++;
                next[i] = j;
            }
            else
            {
                j = next[j];
            }
        }
        /*
        for (int t = 0; t < patternLen; t++)
        cout << next[t] << " ";
        cout << endl;
        */
        //在目标串中寻找模式串的个数, i表示 目标串的下标，j表示模式串的下标
        i = j = 0;
        int count = 0;
        while (i < targetLen)
        {
            if (j == -1)
            {
                i++;
                j++;
            }
            if (patternStr[j] == targetStr[i])
            {
                //当完全匹配时，计数+1，为了找下一个完全匹配串，假设没有匹配，进入下一次循环
                if (j == (patternLen - 1))
                {
                    count++;
                    j = next[j];
                }
                else
                {
                    j++;
                    i++;
                }
            }
            else
            {
                j = next[j];
            }
        }
        cout << count << endl;
        n++;
    }
    return 0;
}

欢迎大家提出宝贵意见~~~