三种算法位置一个不差

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

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

把一段字符折成一个数：h = (h × 31 + 字母序号) % 17，a 记 1、b 记 2、c 记 3。

暴力、哈希、KMP 三种写法都给好了。把三个结果对一遍，输出位置和对账结论。

（本题用 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> brute(const string& t, const string& p) {
    vector<int> pos;
    for (int i = 0; i + (int)p.size() <= (int)t.size(); i++) {
        if (t.compare(i, p.size(), p) == 0) pos.push_back(i);
    }
    return pos;
}

const int BASE = 31;
const int MOD = 17;

int hs(const string& s) {
    int h = 0;
    for (char c : s) h = (h * BASE + (c - 'a' + 1)) % MOD;
    return h;
}

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;
}

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

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + to_string(v[i]);
    return s;
}

vector<int> by_hash(const string& t, const string& p) {
    vector<int> pos;
    int hp = hs(p);
    for (int i = 0; i + (int)p.size() <= (int)t.size(); i++) {
        string w = t.substr(i, p.size());
        if (hs(w) == hp && w == p) pos.push_back(i);
    }
    return pos;
}

int main() {
    vector<int> a = brute(T, P), b = by_hash(T, P), c = kmp(T, P);
    // TODO: 三个结果必须完全一样（vector 可以直接用 == 比），一样就是「一致」
    string verdict = "不一致";
    cout << join(a) << "/" << verdict << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

三种算法位置一个不差

更多题目

全部评论