KMP算法

一、KMP是什么

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在文本中查找模式。它的核心思想是利用已经匹配的信息来避免重复匹配，从而提高效率。

二、暴力字符串匹配

• 暴时间复杂度O（n * m）

//大概是这样的，可能有差别，但是模板基本上是这样
for (int i = 0; i < m;)
{
    int j = 0;
    while (i < m && j < n && s[i++] == p[j++]);
    if (j == n)
    {
        cout << i - j << " ";
    }
    i = j + 1;
}

三、 KMP匹配

时间复杂度O(n)

3.1 算法理解

先理解一下专有名词

• P为模板串，比较短的字符串。

• S为模式串，比较长的字符串。

• 非平凡前缀：除了最后一个字符外，一个字符串的全部头部组合。

• 非平凡后缀：除了第一个字符外，一个字符串的全部尾部组合。

• 部分匹配值：前缀和后缀最长共有的元素的长度， 用next[]数组存储。

3.2 KMP的中心思想

1. 求next[]数组
2. 匹配字符串

求next[]数组：自己和自己匹配字符串而来的,前缀和后缀最长共有的元素的长度,next[]储存的是最长能匹配前缀子串结尾字符的下标。

若字符串p为ababac

next[]数组为：

2：匹配字符串

完整代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
int ne[N];

void HandleNextArr(char str[]){
    // 下标从2开始,自身匹配，第一个数据不用计算
    for(int i = 2, j = 0; i <= n; i ++) { //求next数组
        while (j && str[i] != str[j + 1]) j = ne[j];
        if (str[i] == str[j + 1]) j ++;
        ne[i] = j;
    }
}

void MatchStr(char p[], char s[]){
    HandleNextArr(p);
    for (int i = 1, j = 0; i <= m; i ++) {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++;
        if (j == n) {
            cout << i - n << " ";
            j = ne[j]; 
        }
    }
}

int main() {
    char p[N], s[M];
    cin >> n >> p + 1 >> m >> s + 1;
    MatchStr(p, s);
    return 0;
}