C++字符串模式匹配KMP算法中的next数组算法及C++实现

一致、问题讲述:

对此有数单字符串S、T,找到T在S中第一软面世的序曲位置,若T未当S中冒出,则回-1。

老二、输入描述:

简单单字符串S、T。

其三、输出描述:

字符串T在S中首先不好出现的发端位置,若未出现,则赶回-1。

季、输入例子:

ababaababcb
ababc

五、输出例子:

5

六、KMP算法解析:

KMP算法分为两步,第一步是算next数组,第二步是因next数组通过比节省的道回溯来比较有限只字符串。

网直达差文章关于next数组的角标含义略有差别,这里获得参考文献中王红梅《数据结构(C++版)》的next定义。

设长字符串为S,短字符串为T,next数组的长度和短字符串T的长一致,next[j]代表使T[0]~T[k-1]=T[j-k]~T[j-1]起的最为酷k值。

当T=”ababc”时,next=[-1,0,0,1,2]。

浅显的说道,next[j]意味着了从0往后查k个假名和于j-1往前方查k个字母,这k个字母按角标排列,正好完全平等的太酷k值,其用意是减掉回溯的距离,从而减少比较次数。

基于《数据结构(C++版)》KMP算法的伪代码可以据此如下伪代码表述:

1. 在串S和串T中分别设置比较的起始下标i和j;
2. 重复下述操作,直到S或T的所有字符均比较完毕;
    2.1 如果S[i]等于T[j],继续比较S和T的下一对字符;
    2.2 否则将下标j回溯到next[j]的位置,即j = next[j];
    2.3 如果j等于-1,则将下标i和j分别加1,准备下一趟比较;
3. 如果T中所有字符均比较完毕,则返回匹配的i-j;
    否则返回-1;

KMP算法的C++代码如下:

 1 int KMP(string S, string T)
 2 {
 3     vector<int> next = getNext(T);
 4     int i = 0, j = 0;
 5     while (S[i] != '\0' && T[j] != '\0')
 6     {
 7         if (S[i] == T[j])
 8         {
 9             ++i;
10             ++j;
11         }
12         else
13         {
14             j = next[j];
15         }
16         if (j == -1)
17         {
18             ++i;
19             ++j;
20         }
21     }
22     if (T[j] == '\0')
23         return i - j;
24     else
25         return -1;
26 }

修被只有吃来next数组的概念,算法留给读者就,这里我们拿其成功。

因书被next数组的定义,当T=”ababc”时,

j=0时,next[0] = -1;

j=1时,next[1] = 0;

通下去的next数组要进行测算,

j=2时,T[0]≠T[1],则next[2] = 0;

j=3时,由于事先都比过T[0]与T[1]切莫思量等,所以不用比较T[0~1]与T[1~2](一定不思量当),直接比较T[0]=T[2],则next[3]
= 1;

j=4时,由于next[3] =
1可知T[0]=T[2],所以可以直接比较T[1]=T[3],可得T[0~1]与T[2~3],则next[4]
= 2;

再有雷同栽状况可省计算next的时日,这里换一个加上一些的字符串说明这种情景,当T=”ababaababcb”时,

j=4时,我们算出next[4] = 2(ab=ab);

j=9时,我们计算出next[9] = 4(abab=abab);

j=10时,next[9] =
4可知T[0~3]=T[5~8],直接比较T[9]=’c’和T[4]=’a’不相等,由next[4]为2可得T[0-1]和T[2-3]重新为曾解、由已看清到T[9]与T[4]可得T[7-8]和T[2-3]重复为都知晓,所以可以推测出T[0-1]与T[7-8]啊重复字符,可直接判断T[9]与T[next[4]],即T[9]与T[2],从而省略重复判断T[0-1]与T[7-8]。

计量next数据的C++代码如下:

 1 vector<int> getNext(string T)
 2 {
 3     vector<int> next(T.size(), 0);            // next矩阵,含义参考王红梅版《数据结构》p84。
 4     next[0] = -1;                            // next矩阵的第0位为-1
 5     int k = 0;                            // k值
 6     for (int j = 2; j < T.size(); ++j)        // 从字符串T的第2个字符开始,计算每个字符的next值
 7     {
 8         while (k > 0 && T[j - 1] != T[k])    
 9             k = next[k];
10         if (T[j - 1] == T[k])
11             k++;
12         next[j] = k;
13     }
14     return next;                            // 返回next矩阵
15 }

内部,第8、9行为上述T=”ababaababcb”,j=10时起的气象。第10、11作为类似T[0]=T[2]的较成的图景。第12表现看似next[3]
= 1的赋值。

七、完整程序

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 vector<int> getNext(string T)
 8 {
 9     vector<int> next(T.size(), 0);            // next矩阵,含义参考王红梅版《数据结构》p84。
10     next[0] = -1;                            // next矩阵的第0位为-1
11     int k = 0;                            // k值
12     for (int j = 2; j < T.size(); ++j)        // 从字符串T的第2个字符开始,计算每个字符的next值
13     {
14         while (k > 0 && T[j - 1] != T[k])    
15             k = next[k];
16         if (T[j - 1] == T[k])
17             k++;
18         next[j] = k;
19     }
20     return next;                            // 返回next矩阵
21 }
22 
23 int KMP(string S, string T)
24 {
25     vector<int> next = getNext(T);
26     int i = 0, j = 0;
27     while (S[i] != '\0' && T[j] != '\0')
28     {
29         if (S[i] == T[j])
30         {
31             ++i;
32             ++j;
33         }
34         else
35         {
36             j = next[j];
37         }
38         if (j == -1)
39         {
40             ++i;
41             ++j;
42         }
43     }
44     if (T[j] == '\0')
45         return i - j;
46     else
47         return -1;
48 }
49 
50 int main()
51 {
52     string S = "ababaababcb";
53     string T = "ababc";
54     int num = KMP(S, T);
55     cout << num;
56     return 0;
57 }

参考文献:

[1]王红梅, 胡明, 王涛. 数据结构(C++版)[M]. 北京:清华大学出版社,
2011:83-85.

[2]牛客网.
串的模式匹配[DB/OL]. https://www.nowcoder.com/practice/084b6cb2ca934d7daad55355b4445f8a?tpId=49&&tqId=29363&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking