KMP字符串查找算法

KMP算法的重点是寻找next数组，程序如下：

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

class Solution
{
public:
    int KMPSearch(string text, string pattern, vector<int> next)
    {
        int i = 0;
        int j = 0;
        while (i<text.size() && j<int(pattern.size()))
        {
            if (j == -1 || pattern[j] == text[i])
            {
                i++;
                j++;
            }
            else
            {
                j = next[j];
            }
        }

        if ( j == pattern.size())
            return i - j;
        else
            return -1;
    }

    void GetNext(string pattern, vector<int>& next)
    { 
        next[0] = -1;
        int start = -1;
        int end = 0;
        while (end < pattern.size() - 1)
        {
            if (start == -1 || pattern[start] == pattern[end])
            {
                ++start;
                ++end;
                next[end] = start;
            }
            else
            {
                start = next[start];
            }
        }
    }
};

int main()
{
    Solution sol;
    vector<int> next(7, 0);
    string text("AAAAABBC ABCDAB ABCDABBDCDABDE ABCDABD");
    string pattern("ABCDABD");
    sol.GetNext(pattern, next);
    cout << sol.KMPSearch(text, pattern, next) << endl;
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。