c++ kmp算法（c语言kmp算法）

目录

• KMP算法
  • 步骤1：先计算子串中的前后缀数组Next
    • C++代码：
  • 步骤2：查找子串在母串中出现的位置。
• 总结

KMP算法

KMP算法作用：字符串匹配

例如母串S = “aaagoogleaaa”;

子串T= “google”;

步骤1：先计算子串中的前后缀数组Next

g	o	o	g	l	e
next[0]	next[1]	next[2]	next[3]	next[4]	next[5]
-1	0	0	0	1	0

C++代码：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

//步骤1： void GetNext(string Tsub, vector<int>& Next) { int j = 0, k = -1; Next[0] = k; while (j < Tsub.length() - 1) { if (k == -1 || Tsub[j] == Tsub[k]) { Next[++j] = ++k; } else { k = Next[k]; } } }

步骤2：查找子串在母串中出现的位置。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

//步骤2： int KMP(string S, string T, vector<int> Next) { int i = 0, j = 0; int m = S.length(); int n = T.length(); while (i < m && j < n) { if (j == -1 || S[i] == T[j]) { i++; j++; } else { j = Next[j]; } } if (j == n) { return i - j; } else { return -1; } }

结合上面两个步骤写出完整代码：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

#include <iostream> #include <vector> using namespace std; //步骤1： void GetNext(string Tsub, vector<int>& Next) { int j = 0, k = -1; Next[0] = k; while (j < Tsub.length() - 1) { if (k == -1 || Tsub[j] == Tsub[k]) { Next[++j] = ++k; } else { k = Next[k]; } } } //步骤2： int KMP(string S, string T, vector<int> Next) { int i = 0, j = 0; int m = S.length(); int n = T.length(); while (i < m && j < n) { if (j == -1 || S[i] == T[j]) { i++; j++; } else { j = Next[j]; } } if (j == n) { return i - j; } else { return -1; } } int main() { string S = "aaagoogleaaa"; string T = "google"; vector<int> Next(T.length()); GetNext(T, Next); int retVal = KMP(S, T, Next); if (retVal == -1) { std::cout << "can't Index" << std::endl; } else { std::cout << "Index :" << retVal << std::endl; } return 0; }

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注服务器之家的更多内容！

原文链接：https://blog.csdn.net/m0_49939824/article/details/119708086