预处理摊到十段文本上

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

模式固定是 ababc，文本一段接一段地来，每段都长 abababcababcabababc 那样。next 表只需要算一次。按暴力1段 / 暴力10段 / KMP1段 / KMP10段的顺序输出比较次数。

（本题用 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 next_cmp(const string& p) {
    vector<int> f(p.size(), 0);
    int k = 0, c = 0;
    for (int i = 1; i < (int)p.size(); i++) {
        while (k > 0 && p[i] != p[k]) {
            k = f[k - 1];
            c++;
        }
        c++;
        if (p[i] == p[k]) k++;
        f[i] = k;
    }
    return c;
}

int total(const string& kind, int n_texts) {
    // TODO: "brute" → 每段都花 brute_cmp(T, P)，没有预处理
    // TODO: "kmp"   → next 表只算一次（next_cmp(P)），之后每段花 kmp_cmp(T, P)
    (void)kind;
    (void)n_texts;
    return -1;
}

int main() {
    cout << total("brute", 1) << "/" << total("brute", 10) << "/" << total("kmp", 1) << "/" << total("kmp", 10) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

预处理摊到十段文本上

更多题目

全部评论