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

在字符串 str 中 匹配模式串 pattern

1. 计算模式串的 next 数组；

2. 在字符串中匹配模式串；当一个字符匹配时，str[i++], pattern[k++] 继续匹配下一个字符；当当前字符不匹配时。依据 next 数组移动模式字符串。k = next[k]

next 数组：描写叙述模式串中最长同样的前缀和后缀的长度。

#include <iostream>

using namespace std;

class Solution {

public:

    void GetNext(string pattern) {

        next = new int[pattern.size()];

        next[0] = -1;

        int k = -1;

        int j = 0;

        while (j < pattern.size()-1) {

            if (k == -1 || pattern[j] == pattern[k]) {

                ++j;

                ++k;

                if (pattern[j] != pattern[k]) {

                    // 此时的 pattern[k] 即为 pattern[next[j] ]

                    next[j] =k;

                } else {

                    // 假设 pattern[j] == pattern[next[j]]。则 k = next[k]

                    next[j] = next[k];

                }

            } else {

                k = next[k]; // 不匹配。向前找前缀。相当于用模式串匹配模式串

            }

        }

    }

    int KMPSearch(string str, string pattern) {

        if (str.size() == 0 || pattern.size() == 0)

            return -1;

        GetNext(pattern);

        int j = 0; // 待匹配串索引

        int k = 0; // 模式串索引

        while (j < str.size() && k < (int)pattern.size()) {  //注意，负数不能和 size_t 的无符号数作比較

            if (k == -1 || str[j] == pattern[k]) {

                ++k;

                ++j;

            } else {

                k = next[k]; // 不匹配，移动模式串

            }

        }

        if (k == pattern.size())

            return j-k;

        else

            return -1;

    }

    Solution() {

        next = NULL;

    }

    ~Solution() {

        if (next != NULL)

            delete []next;

        next = NULL;

    }

private:

    int *next;

};

int main()

{

    string str = "abacababc";

    string pattern = "abab";

    Solution sol;

    cout << sol.KMPSearch(str, pattern) << endl;

}

相关：

Implement strStr() | 实现字符串查找函数: 用 hash-code 的方法实现字符串的搜索；easy实现，须要支持大数。

字符串匹配的Boyer-Moore算法：思路简单，性能更好，但不easy计算得到好后缀表和坏字符表