KMP算法

给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。

1、暴力匹配，时间复杂度为 $O (n m)$

 1 #include<iostream>
 2 #include<string>
 3 
 4 using namespace std;
 5 
 6 int stringSearch(string p, string m)
 7 {
 8     int i = 0, j = 0;
 9     int psize = p.size(), msize = m.size();
10     while (i < psize&&j < msize)
11     {
12         if (p[i] == m[j])
13         {
14             ++i;
15             ++j;
16         }
17         else
18         {
19             i = i - j + 1;
20             j = 0;
21         }
22     }
23     if (j = msize)
24         return i - j;
25     return -1;
26 }
27 
28 int main()
29 {
30     string p = "BBC ABCDAB ABCDABCDABDE";
31     string m = "ABCDABD";
32     int idx=stringSearch(p, m);
33     cout << idx << endl;
34 
35     return 0;
36 }

2、KMP算法

 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 void getNext(string m, int next[])
 7 {
 8     int m_len = m.size();
 9     int i = 0;   
10     int j = -1;
11     next[0] = -1;
12 
13     while (i < m_len)
14     {
15         if (j == -1 || m[i] == m[j])
16         {
17             i++;
18             j++;
19             next[i] = j;
20         }
21         else
22             j = next[j];
23     }
24 }
25 
26 int KMP(string s, string m, int next[])
27 {
28     getNext(m, next);
29 
30     int i = 0;  
31     int j = 0;  
32     int s_len = s.size();
33     int m_len = m.size();
34 
35     while (i < s_len && j < m_len)
36     {
37         if (j == -1 || s[i] ==m[j])  
38         {
39             i++;
40             j++;
41         }
42         else
43             j = next[j];  
44     }
45 
46     if (j == m_len)  
47         return i - j;
48 
49     return -1;
50 }
51 
52 int main()
53 {
54     int next[100] = { 0 };
55     string s = "bbc abcdab abcdabcdabde";
56     string m = "abcdabd";
57     cout << KMP(s, m, next) << endl;
58 
59     return 0;
60 }

KMP算法的时间复杂度还是很稳定的。
平均时间复杂度为 Θ(m+n)。
最好时间复杂度为 O(m+(n−m))=O(n)。它发生在主串和模式串字符都不相同的情况下，例如，主串为abcdefghijk，模式串为+-*/。
最差时间复杂度为 O(m+n)。它发生在主串和模式串都为相同的字符的情况下，例如，主串为aaaaaaaaaaaaaaaaaaaaa，模式串为aaaa。

参考：

https://www.cnblogs.com/yjiyjige/p/3263858.html

https://61mon.com/index.php/archives/183/

https://www.cnblogs.com/zhangtianq/p/5839909.html