KMP算法C++实现

//参考资料 
//https://segmentfault.com/a/1190000004254889
//https://www.cnblogs.com/c-cloud/p/3224788.html
#include <windows.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution
{
public:
    int strStr(string txt, string pat) 
    {
        //边界条件 
        if (pat.empty())
        {
            return 0;
        }
        int tlen = txt.size();
        int plen = pat.size();
        if (tlen < plen)
        {
            return -1;
        }

        //计算next数组 
        vector<int> next(plen, -1);
        calcNext(pat, next);
        for (int i = 0; i < next.size(); i++)
        {
            cout << next[i] << " ";
        }
        cout << endl;

        //字符串匹配 
        //t是客人，p是主人，怎么能让客人回退呢？不匹配就不匹配呗，还让我回退！
        //t不回退，p回退 
        for (int t = 0, p = 0; t < tlen; t++)
        {
            while (p > 0 && txt[t] != pat[p])
            {
                p = next[p-1];
            }
            if (txt[t] == pat[p])
            {
                p++;
            }

            //返回结果 
            //p == plen 表示在txt中出现了第一个能够成功匹配pat的字符串
            //返回这个字符串的起始下标
            if (p == plen)
            {
                return t-plen+1;
            }
        }
    }

    void calcNext(const string &pat, vector<int> &next)
    {
        //计算next数组
        //p是主人，k是仆人，怎么能让主人回退呢？不匹配就不匹配呗，还让我回退！
        //p不回退，k回退 
        int plen = pat.size();
        next[0] = 0;
        for (int p = 1, k = 0; p < plen; p++)
        {
            while (k > 0 && pat[p] != pat[k])
            {
                k = next[k-1];
            }
            if (pat[p] == pat[k])
            {
                k++;
            }

            //赋值 
            next[p] = k;
        }
    }
};

int main(int argc, char* argv[])
{
    string txt = "ababababababb";
    string pat = "abababb";

    Solution s;
    cout << s.strStr(txt, pat) << endl;

    system("pause");
    return 0;
}

执行结果：
0 0 1 2 3 4 0
6