KMP算法C代码实现

Love The Way You Lie 2022-07-28 09:49 275阅读 0赞

一、初识KMP

理解KMP算法需要关注2个问题：（请注意：字符串下标从0开始。）

当i指针与j指针失配时：

1、当母串和模式串不匹配时，i指针为什么不需要回溯？

2、当母串和模式串不匹配时，i指针不回溯，那么j指针应该移动到哪？

通过解释第1个问题，我来引出第2个问题。（其实第1个问题，你不明白，不影响你研究第2个问题，你也可以理解了第2个问题后来分析第1个问题。）

对于母串S和模式串T，如果母串的指针i处与模式串的j处失配，假设母串存在回溯i到back(i) （匹配前的i < back(i) < i），有与模式串的从0开始的模式串有一段一样长的“段落”，这个母串的段落只有是S\[back(i)\] 至S\[i-1\]才有意义，如果从S\[back(i)\] 至S\[i-1\]的过程中就已经不匹配了，那回溯至这个back(i)就更没有必要了。 即S\[back(i) ...i-1\]=T\[0...x\] ，x = i-1-back(i)。又因为前面失配时存在同样长度的段落，即S\[back\[i\]...i-1\] = T\[ j -1-x...  j-1\]，所以T\[0...x\] = T\[j-1-x ...j-1\]。

这其实就转化成了i不变，j指针移动到x+1（后面讨论用next\[j\] 表示 x +1 ）的问题，即问题2。

你可以用back(i) = i - 1 - x = i - next\[j\]来验证我的分析，注意我的字符串的下标是从0开始的。

我们来讨论问题2:

![Center][]

当 i与j 不匹配的时候，图1所示，因为有k < j 并且 Si-j... Si-1  = T0...Tj-1 ，所以Si-k...Si-1  = Tj-k...Tj-1。

由于S的i不回溯，图2所示，且需要与T的k指针比较，则Si-k...Si-1 = T0...Tk-1。所以T0...Tk-1 = Tj-k...Tj-1。

令next\[j\] = k 表示当模式串的j与主串相应字符i不匹配时，在模式中需重新与主串中该字符i比较的字符的位置。则next\[j\]表示为：

![Center 1][]

那我们如何求取next\[j\]呢？ 用递推的方式，即通过已知的next\[0\] = -1, 来推出后面如next\[1\]、next\[2\]、next\[3\]... 的值。最关键的是找出next\[j + 1\] 与next\[j\]的关系。

所以我们来研究next\[j  + 1\] 与 next\[j\]的关系。(当然我们的前提是next\[j\] = k，不要忘记哦）

因为 next\[j\] = k，这意味着T0...Tk-1= Tj-k ...Tj-1 （0 < k < j，并且k是满足这个等式的max(k)。）

那此时next\[j + 1\] 等于多少呢？

分两种情况：

1、如 Tk = Tj，则T0...Tk-1Tk = Tj-k...Tj-1Tj 。这表示next\[j + 1\] = k + 1，又由于k = next\[j\] ，所以next\[j + 1\] = next\[j\] + 1 ，故根据next\[j\]可求得next\[j+1\]。

2、较为难理解的是Tk ≠ Tj 。此时显然T0...Tk-1Tk  ≠ Tj-k...Tj-1Tj 。如果我们把\#\#\#Tj-k...Tj-1Tj\#\#\# 表示母串，以T0...Tk-1Tk\#\#\#表示模式串。显然当Tj与Tk失配的时候，Tj应该与模式串的k'=next\[k\] 来匹配。此时应该有T0...Tk'-1 = Tk-k'...Tk-1=Tj-k'...Tj-1。(1 < k' < k < j）。 注意，此时我们需要关注Tk‘与Tj的关系，关注Tk'与Tk的关系对于解决next\[j+1\]没有用处！

此时也应该分两种情况，即

1）、如果Tk‘= Tj ，所以T0...Tk'-1Tk' = Tj-k'...Tj-1Tj 。所以next\[j + 1\] = k' + 1，由于k' = next\[k\]，所以next\[j + 1\] = next\[k\] + 1，故根据next\[k\]可求得next\[j+1\]。

2）、如果Tk' ≠ Tj，我们就要寻找更小的k''来匹配Tj。这当然也是有两种情况，即Tk'' = Tj 或Tk"≠ Tj，对于前者，next\[j + 1\] = k" + 1 = next\[k'\] + 1,寻找结束；对于后者，继续寻找更小的k'''、k''''，当然寻找不能无限制下去，结束的条件就是next\[0\] = -1 或你提前找到了你的k ?（如果你找到了你的k?，显然next\[j + 1\] = k？+ 1，寻找结束）。

现在来分析说明get\_next函数（见代码实现部分）的正确性。

我们需要证明在next\[j\]==k的基础上得到next\[j+1\]=(k/next\[k\]/.../-1之一） + 1 ，考察字符串abaabcac，下标从0开始，规定next\[0\]=-1

当j=0, k=-1，满足next\[j\]=k，因为k=-1，我们可以得到next\[j+1\]=k+1， 即next\[1\]=0；

当j=1, k=0， 满足next\[j\]=k，因为T\[j\] ≠T\[k\]，但next\[k\]=-1，我们可以得到next\[j+1\]=next\[k\]+1， 即next\[2\]=0；

当j=2, k=0， 满足next\[j\]=k，因为T\[j\]=T\[k\]， 我们可以得到next\[j+1\]=k+1， 即next\[3\]=1；

当j=3, k=1， 满足next\[j\]=k，因为T\[j\]≠T\[k\]，但T\[j\]=T\[next\[k\]\]， 我们可以得到next\[j+1\] = next\[k\]+1， 即next\[2\]=1；

由前面next\[j\] = k ，我们根据get\_next函数可以证明一般性结论next\[j+1\] = (k/next\[k\]/.../-1之一） + 1。

二 、代码实现

**\[cpp\]**  [view plain][]  [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  \#include <stdio.h>  
2.  \#include <string.h>  
3.    
4.  **int** next\[32\] = \{-999\};  
5.    
6.  /\* 返回模式串T在母串S中第pos个字符的位置 \*/  
7.  /\* 调试小技巧 print x = value 或 set var x = value 可以改变gdb运行时变量的值 \*/  
8.  **int** index\_BM(**char** \*S, **char** \*T, **int** pos)  
9.  \{  
10.     **int** i;  
11.     **int** j;  
12.   
13.     i = pos;  
14.     j = 0;   
15.   
16.     **while** ( (i < strlen(S)) && (j < strlen(T)) )  
17.     \{  
18.         **if** (S\[i\] == T\[j\])  
19.         \{  
20.             i++;  
21.             j++;  
22.         \}  
23.         **else**  
24.         \{  
25.             i = i - j + 1;   
26.             j = 0;  
27.         \}  
28.     \}  
29.   
30.     /\* 注意strlen(T)意味着j的取值范围为0 ~ (strlen(T) - 1) \*/  
31.     **if** (strlen(T) == j)  
32.     \{  
33.         **return** i - strlen(T);  
34.     \}  
35.     **else**  
36.     \{  
37.         **return** -1;  
38.     \}  
39. \}  
40.   
41. **void** get\_next(**char** \*T, **int** \*next)  
42. \{  
43.     **int** k = -1;  
44.     **int** j = 0;  
45.   
46.     next\[j\] = k;  
47.   
48.     **while** (j < strlen(T))  
49.     \{  
50.         **if** ( (k == -1) || (T\[j\] == T\[k\]) ) //注意等号是==，而不是=  
51.         \{  
52.             ++k; // 注意是先加后使用  
53.             ++j;  
54.             next\[j\] = k;  
55.         \}  
56.         **else**  
57.         \{  
58.             k = next\[k\];   
59.         \}  
60.     \}  
61. \}  
62.   
63. **int** index\_KMP(**char** \*S, **char** \*T, **int** pos)  
64. \{  
65.     **int** i;  
66.     **int** j;  
67.   
68.     i = pos;  
69.     j = 0;   
70.   
71.     **while** ( (i < strlen(S)) && (j < strlen(T)) )  
72.     \{  
73.         /\* j = -1 表示next\[0\], 说明失配处在模式串T的第0个字符。所以这里特殊处理，然后令i+1和j+1。\*/  
74.         **if** ( (j == -1)  || S\[i\] == T\[j\])  
75.         \{  
76.             i++;  
77.             j++;  
78.         \}  
79.         **else**  
80.         \{  
81.             j = next\[j\];  
82.         \}  
83.     \}  
84.   
85.     **if** (strlen(T) == j)  
86.     \{  
87.         **return** i - strlen(T);  
88.     \}  
89.     **else**  
90.     \{  
91.         **return** -1;  
92.     \}  
93. \}  
94.   
95. **void** print\_next(**int** next\[\], **int** n)  
96. \{  
97.    **int** i;  
98.   
99.    **for** (i = 0; i < n; i++)   
100.    \{  
101.        printf("next\[%d\] = %d\\n", i, next\[i\]);  
102.    \}  
103. \}  
104.   
105. **int** main(**void**)  
106. \{  
107.     **char** \*s = "ababcabcacbab";  
108.     **char** \*t = "abcac";  
109.     **int** pos = 0;  
110.     **int** index;  
111.   
112.     printf("================ BM ==============\\n");  
113.     index = index\_BM(s, t, pos);  
114.     printf("index = %d\\n", index);  
115.   
116.     printf("================ KMP ==============\\n");  
117.     get\_next(t, next);  
118.     print\_next(next, strlen(t));  
119.   
120.     index = index\_KMP(s, t, pos);  
121.     printf("index = %d\\n", index);  
122. \}  
123.

[Center]: /images/20220724/fbbf337df76f4e2cbd7fcff292ee25d6.png
[Center 1]: /images/20220724/00725770f80047be886bb12e7dabb1bd.png
[view plain]: http://blog.csdn.net/xumin330774233/article/details/14441809#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/93777
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/93777/fork