KMP遍历算法

KMP算法是一种改进的字符串匹配算法，关键是利用匹配后失败的信息，尽量减少模式串（W）与主串（T）的匹配次数以达到快速匹配的目的。具体实现就是实现一个next() 函数，函数本身包含了模式串的局部匹配信息。时间复杂度 O(m+n)。

如果考虑一般的方法，我们可以将T[0]和W[0]进行匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1]跟W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，时间复杂度为O(m*n)。

学习代码：

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>



using namespace std;

//get_next函数 

vector<int> get_next(string b)    //用vector来保存子串b的next数组

{

    vector<int> result;   //添加元素并且默认赋值为0，建立一个空的容器就

    int i, j;

    i = 0;

    j = -1;

    result.push_back(-1);    //将容器首元素赋值，作为标识使用

    while (i < b.size() - 1)

    {

        if (j == -1 || b[i] == b[j])    //b[i]表示后缀的单个字符，b[j]表示前缀的单个字符 

        {

            ++i;              

            ++j;

            //这里的其实是优化重复的字符

            //可以直接用result.push_back(j);代替下面的判断语句

            if (b[i] != b[j])

                result.push_back(j);

            else if (i == 1)

                result.push_back(j);

            else

                result.push_back(result[j]);

        }

        else

            j = result[j];  //若字符不同，前缀字符回溯

    }

    return result;

}

//KMP函数

int KMP(string a, string b)

{

    vector<int> next = get_next(b);  //调用get_text函数

    int i = 0;

    int j = 0;

    //注意size函数返回的类型是string::size_type是无符号数

    //若i<主串的长度且j<子串的长度时，循环继续

    while (i < (int)a.size() && j <(int)b.size())    

    {

        if (j == -1 || a[i] == b[j])  //两字母相等则继续，相对于朴素算法增加了

        {

            ++i;

            ++j;

        }

        else {

            j = next[j];   //若不相等，j退回合适的位置

        }

    }

    if (j == b.size()) 

    {   //这里返回的是匹配字符开始的下标位

        return i - j;

    }

    else {

        return -1;

    }

}



int main()

{

    string str;

    cout << "enter the string:";

    cin >> str;

    string pattern;

    cout << "enter the pattern:";

    cin >> pattern;

    int result = KMP(str, pattern);

    cout << result << endl;

}