Day11:KMP、字典树、AC自动机、后缀数组、manacher
阅读原文时间:2023年08月11日阅读:3

KMP算法

KMP算法是一个著名的字符串匹配算法,效率很高,但是确实有点复杂

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的,那么,它是则呢样来消除回溯的呢?就是因为它提取并运用了加速匹配的信息!

这种信息就是对于每模式串 t 的每个元素 t j,都存在一个实数 k ,使得模式串 t 开头的 k 个字符(t 0 t 1…t k-1)依次与 t j 前面的 k(t j-k t j-k+1…t j-1,这里第一个字符 t j-k 最多从 t 1 开始,所以 k < j)个字符相同。如果这样的 k 有多个,则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息,采用 next 数组表示,即 next[ j ]=MAX{ k }。

这里并没有将next数组,如果您想看,我推荐这位大佬的博文:点这里

// s[]是长文本,p[]是模式串,n是s的长度,m是p的长度
//求模式串的Next数组:
for (int i = 2, j = 0; i <= m; i++) {
    while (j && p[i] != p[j + 1])
        j = ne[j];
    if (p[i] == p[j + 1])
        j++;
    ne[i] = j;
}
// 匹配
for (int i = 1, j = 0; i <= n; i++) {
    while (j && s[i] != p[j + 1])
        j = ne[j];
    if (s[i] == p[j + 1])
        j++;
    if (j == m) {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

831. KMP字符串

给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P在字符串 S

中多次作为子串出现。求出模式串 P在字符串 S中所有出现的位置的起始下标。

输入格式

第一行输入整数 N,表示字符串 P的长度。

第二行输入字符串 P。

第三行输入整数 M,表示字符串 S的长度。

第四行输入字符串 S。

输出格式

共一行,输出所有出现位置的起始下标(下标从 0

开始计数),整数之间用空格隔开。

数据范围

1≤N≤105

1≤M≤106

输入样例

3
aba
5
ababa

输出样例:

0 2


#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main() {
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1])
            j = ne[j];
        if (p[i] == p[j + 1])
            j++;
        ne[i] = j;
    }
    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) {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}

详见字符串算法——KMP算法C++详解

字典树

注:csdn的不怕困难的博客即将搬家至本博客,敬请期待!

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器