字符串匹配：KMP

参考：从头到尾彻底理解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 的方法实现字符串的搜索；容易实现，需要支持大数。

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