ToB企服应用市场:ToB评测及商务社交产业平台

标题: KMP算法 [打印本页]

作者: 忿忿的泥巴坨 时间: 2024-6-2 22:13
标题: KMP算法
KMP算法

KMP算法是一个办理模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。
重点是找到字符串的最长公共前后缀。用最长公共前后缀在匹配的同时，实现快速跳转。
KMP的时间复杂度

假设 m为模式串strM的长度，n为待匹配的字符串strN的长度。
时间复杂度为 \(O(m+n)\)
参考文档：
KMP时间复杂度分析
[code]#includeusing namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;const int Maxn = 1e6 + 5;int la, lb;int nxt[Maxn];char a[Maxn], b[Maxn];inline void kmp() { //字符串: 1 ~ lb; nxt[1] = 0; for (int i = 2, j = 0; i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)