KMP字符串查找算法

2015/07/27 42508

清华大佬耗费三个月吐血整理的几百G的资源，免费分享！....>>>

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}