本文主要是介绍kmp算法c++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
kmp算法通过next数组使查找失败时减少跳转后比较的次数来优化字符串查找，next数组存储了前缀和后缀相同的位置信息，类似动规，可以存储查找数组的信息来防止重复查找，最终复杂度可以达到O（n+m）。
以t=“abcabd”字符串为例进行讲解
next数组存储的是当前位置与前面具有相同前缀的长度，同时在查找失败后，可以在失败位置的其哪一个位置对应的next数组值来跳转到具有相同前缀的字符串的下一个位置，这样就可以避免重复验证前缀部分是否和被查找的字符串匹配。
具体的演示可以看和手算方法见「六分钟速通」KMP算法求解流程，up讲的简单明了。视频里pm即为文中的next数组
next[i]里的数字代表包括t[i]在内的部分与前面字符串部分子串相同的长度，同时该数字也是前面相同子串的下一个字符的下标。
这里设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或找到相同前缀为止。
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;void grtnext(char *c, int *nextKMP)
{int len = strlen(c);nextKMP[0] = 0;int k = 0;int j = 1;while (j < len){if (k == 0){if (c[j] == c[k]){nextKMP[j] = 1;k++;}elsenextKMP[j] = 0;j++;continue;}if (c[j] == c[k]){nextKMP[j] = nextKMP[j - 1] + 1;k++;j++;}else{k = nextKMP[k - 1];}}
}
int KMP(char *s, char *t, int *next, int *re)
{int lens = strlen(s);int lent = strlen(t);int i = 0, j = 0;while (i < lens && j < lent){re[0]++;if (s[i] == t[j]){i++;j++;}else{if (j == 0)i++;elsej = next[j - 1];}}if (j == lent)return i - lent;return -1;
}
int trlen(char *s)
{int len = 0;while (s[len] != '\0'){len++;}
}
int main()
{char *c = "aabaac";char *s = "aabaabaaac";int len = strlen(c);int re[2] = {0};int *nextKMP = new int[len];grtnext(c, nextKMP);int k = KMP(s, c, nextKMP, re);// for (int i = 0; i < len; i++)// {// cout << nextKMP[i] << " ";// }
if(k==-1)cout<<"no find"<<endl;
elsecout << k + 1 << endl;cout << re[0]; // 输出比较次数system("pause");
}
这篇关于kmp算法c++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
