KMP算法

为什么要使用kmp算法？：减少字串（T）在主串（S）中不必要的查找
暴力查找：逐个查找每次发现有字符不相符，主串就返回到最初字符的下一个字符，字串返回到最开始

在图中可以发现字符串中某一段是重复的回到最初就加大了搜索难度，所以引入一个next数组来记录最大相同前后缀子串，用于在指针返回的时候不用回到最开头

前后缀

前缀：除去最后一个字符，以第一个字符开头的每一组字符串
后缀：除去开头第一个字符，以最后一个字符结尾的每一组字符串
例如字符串：abcd
它的前缀子串为：a,ab,abc
它的后缀子串为：d,cd,bcd
相同前后缀为：0
这样我们通过统计一个字符串中每一个长度子串的最大相同前后缀我们可以知道字符串中首位元素的重复情况，就可以每次跳回到必要的位置而不是开头
使用next数来对T的最大相同前后缀进行计数：

KMP算法

在对字符串中的字符进行查找时字符串S不会进行回溯，通过对T的回溯来减少一部分元素比较

#include
#include

using namespace std;

//next数组初始化
void InitNext(vector<int> &next, const string& T)
{
    int j = 0;
    next[0] = 0;
    for(int i = 1; i < T.size(); i++) 
    {
        //通过KMP的思想对T字符串进行回溯减少不必要的字符查找
        while(j > 0 && T[i] != T[j]) j = next[j - 1];   
        if(T[i] == T[j]) j++;
        next[i] = j;
    }
}

int KMP(const string &S, const string &T)
{
    if(T.size() == 0) return 0;
    vector<int> next(T.size());
    InitNext(next, T);
    int j = 0;
    for(int i = 0; i < S.size(); i++)
    {
        while(j > 0 && S[i] != T[j]) j = next[j - 1];
        if(S[i] == T[j]) j++;
        if(j == T.size()) return i - T.size() + 1;
    }
    return -1;
}

int main()
{
    string S = "";
    string T = "";
    cin>>S;
    cin>>T;
    cout<<endl;
    int ret = KMP(S, T);
    cout<<ret<<endl;
    system("pause");
    return 0;
}
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