kmp算法c++

kmp算法通过next数组使查找失败时减少跳转后比较的次数来优化字符串查找，next数组存储了前缀和后缀相同的位置信息，雷同动规，可以存储查找数组的信息来防止重复查找，最终复杂度可以达到O（n+m）。
以t=“abcabd”字符串为例进行讲解
next数组存储的是当前位置与前面具有相同前缀的长度，同时在查找失败后，可以在失败位置的其哪一个位置对应的next数组值来跳转到具有相同前缀的字符串的下一个位置，如许就可以制止重复验证前缀部门是否和被查找的字符串匹配。
具体的演示可以看和手算方法见「六分钟速通」KMP算法求解流程，up讲的简单明白。视频里pm即为文中的next数组
next里的数字代表包括t在内的部门与前面字符串部门子串相同的长度，同时该数字也是前面相同子串的下一个字符的下标。
这里设j，k作为下标表示，j为当前盘算的下标，k为前面与当前盘算下标j结尾的子串相同的子串的结尾下标，即具有相同前缀的子串结尾下标。
当k=0时，有两种情况，一是t[j]=t[k],那么此时next[j]=next[j-1]+1，即相同前缀部门变大，如果差别，此时k=0，则next[j]应该为0，即没有相同前缀。
当k!=0时，如果t[k]=t[j],则按上述盘算方法来表示扩大相同前缀，如果t[k]!=t[j]，那么向前找相同前缀，做法时k=next[k-1],因为next数组存储的是当前位置与前面具有相同前缀的长度，则向前查找只必要找到以k-1结尾的相同子串的长度，如果还差别，重复向前查找，直到k=0或找到相同前缀为止。

1. #include <iostream>
2. #include <string.h>
3. #include <stdlib.h>
4. using namespace std;
6. void grtnext(char *c, int *nextKMP)
7. {
8.     int len = strlen(c);
10.     nextKMP[0] = 0;
11.     int k = 0;
12.     int j = 1;
13.     while (j < len)
14.     {
15.         if (k == 0)
16.         {
17.             if (c[j] == c[k])
18.             {
19.                 nextKMP[j] = 1;
20.                 k++;
21.             }
22.             else
23.                 nextKMP[j] = 0;
24.             j++;
25.             continue;
26.         }
27.         if (c[j] == c[k])
28.         {
29.             nextKMP[j] = nextKMP[j - 1] + 1;
30.             k++;
31.             j++;
32.         }
33.         else
34.         {
35.             k = nextKMP[k - 1];
36.         }
37.     }
38. }
39. int KMP(char *s, char *t, int *next, int *re)
40. {
41.     int lens = strlen(s);
42.     int lent = strlen(t);
43.     int i = 0, j = 0;
45.     while (i < lens && j < lent)
46.     {
47.         re[0]++;
48.         if (s[i] == t[j])
49.         {
50.             i++;
51.             j++;
52.         }
53.         else
54.         {
55.             if (j == 0)
56.                 i++;
57.             else
58.                 j = next[j - 1];
59.         }
60.     }
61.     if (j == lent)
62.         return i - lent;
63.     return -1;
64. }
65. int trlen(char *s)
66. {
67.     int len = 0;
68.     while (s[len] != '\0')
69.     {
70.         len++;
71.     }
72. }
73. int main()
74. {
75.     char *c = "aabaac";
76.     char *s = "aabaabaaac";
77.     int len = strlen(c);
78.     int re[2] = {0};
79.     int *nextKMP = new int[len];
80.     grtnext(c, nextKMP);
81.     int k = KMP(s, c, nextKMP, re);
82.     // for (int i = 0; i < len; i++)
83.     // {
84.     //     cout << nextKMP[i] << " ";
85.     // }
86. if(k==-1)cout<<"no find"<<endl;
87. else
88.     cout << k + 1 << endl;
89.     cout << re[0]; // 输出比较次数
90.     system("pause");
91. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。