第二步哈希版别忘确认

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

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

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

第二步：写哈希版，并且和第一步的基准线对账。

（本题用 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;
}

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> out;
    int hp = hs(p);
    for (int i = 0; i + (int)p.size() <= (int)t.size(); i++) {
        if (hs(t.substr(i, p.size())) == hp) {
            // TODO: 哈希对上之后，再逐字符确认一次（那一段真的等于 p）才收进 out
        }
    }
    return out;
}

int main() {
    vector<int> a = brute(T, P), b = by_hash(T, P);
    cout << join(b) << "/" << (a == b ? "一致" : "不一致") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

第二步哈希版别忘确认

更多题目

全部评论