平均差不多最坏差很多

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

两组对照：一组是普通文本 abababcababcabababc 配 ababc，一组是最坏情况（24 个 a 配 6 个 a）。四个数一起输出：普通暴力、普通 KMP、最坏暴力、最坏 KMP。

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

提交你的答案

请登录后提交答案。

去登录

← 把选型写成一个函数需求没说清时该回答什么 →

更多题目

代码编辑器

语言： 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;
}

int brute_cmp(const string& t, const string& p) {
    int c = 0;
    for (int i = 0; i + (int)p.size() <= (int)t.size(); i++) {
        for (int j = 0; j < (int)p.size(); j++) {
            c++;
            if (t[i + j] != p[j]) break;
        }
    }
    return c;
}

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

int main() {
    string t24(24, 'a'), p6(6, 'a');
    // TODO: 左边一组：普通文本 T 配模式 P，暴力和 KMP 各多少次
    // TODO: 右边一组：最坏文本 t24 配模式 p6，暴力和 KMP 各多少次
    int a = -1, b = -1, c = -1, d = -1;
    cout << a << "/" << b << "/" << c << "/" << d << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

平均差不多最坏差很多

更多题目

全部评论