【KMP】字符串匹配

xiao-gan 2021-09-05 原文

问题：

字符串s=”ABBCABCDABDADSBC”，p=”ABCDABD”，问p在s中第一次出现的索引，未找到则返回-1

思路：

暴力求解：时间复杂度O(m*n)，其中m、n分别为s、p的长度

KMP算法：时间复杂度O(m+n)

利用next[]，存储字符串p中的前后缀相同的长度。

即next[j]=p[0~j-1]中前缀和后缀相同的长度，next[0]=-1，难点在于求next数组

 1 #include <iostream>
 2 #include <string>
 3 #include <string.h>
 4 #include <map>
 5 #include <set>
 6 #include <list>
 7 #include <vector>
 8 #include <deque>
 9 #include <unordered_set>
10 #include <algorithm>
11 #include <unordered_map>
12 #include <stack>
13 #include <cstdio>
14 #include <memory>
15 using namespace std;
16 
17 int* getNext(string &s)
18 {
19     int *next = new int[s.size()];
20     next[0] = -1;
21     int k = -1, j = 0;
22     while (j < s.size() - 1)
23     {
24         if (k == -1 || s[j] == s[k])
25         {
26             j++;
27             k++;
28             next[j] = k;
29         }
30         else
31         {
32             k = next[k];
33         }
34     }
35     return next;
36 }
37 
38 int kmp(string &s, string &p,int next[])
39 {
40     int i = 0, j = 0;
41     while (i < s.size() && j < p.length())
42     {
43         if (j == -1 || s[i] == p[j])
44         {
45             i++;j++;
46         }
47         else
48         {
49             j = next[j];    //j跳到相同前缀的后面
50         }
51     }
52     if (j == p.size())
53         return i-j;
54     else
55         return -1;
56 }
57 
58 int main()
59 {
60     string s = "ABBCABCDABDADSBC", p = "ABCDABD";
61     cout << kmp(s, p, getNext(p))<<endl;
62     int *a = getNext(p);
63     for (int i = 0;i < 7;i++)
64         cout << a[i] << \' \';
65     cout << endl;
66     return 0;
67 }