KMP 的回退次数是零

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

一段文本 abababcababcabababc（19 个字符，下标从 0 起）和一个模式 ababc。

数出 KMP 的比较次数，再记下文本指针最远走到哪个下标、回退了几次，和暴力的 39 次放在一起输出。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 写一个不回退的 KMP 三种算法位置一个不差 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const string T = "abababcababcabababc";
const string P = "ababc";

vector<int> build_next(const string& p) {
    vector<int> f(p.size(), 0);
    int k = 0;
    for (int i = 1; i < (int)p.size(); i++) {
        while (k > 0 && p[i] != p[k]) k = f[k - 1];
        if (p[i] == p[k]) k++;
        f[i] = k;
    }
    return f;
}

void kmp_stats(const string& t, const string& p, int& cmps, int& far, int& back) {
    vector<int> f = build_next(p);
    cmps = 0, far = -1, back = 0;
    int k = 0, prev_i = -1;
    for (int i = 0; i < (int)t.size(); i++) {
        while (k > 0 && t[i] != p[k]) {
            k = f[k - 1];
            cmps++;
        }
        cmps++;
        if (t[i] == p[k]) k++;
        if (k == (int)p.size()) k = f[k - 1];
        // TODO: far 记下文本指针走到过的最大下标
        // TODO: i 比上一轮还小才算一次回退（back 加 1）
        prev_i = i;
    }
}

int main() {
    int c, f, b;
    kmp_stats(T, P, c, f, b);
    cout << 39 << "/" << c << "/" << f << "/" << b << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

KMP 的回退次数是零

更多题目

全部评论