交付五条验收一起过

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

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

四个要找的词 he、she、his、hers，一段文本 ushershishe（11 个字符，下标从 0 起）。

最后一步：五条验收条款前两条已经写好。补全第三条（KMP 和基准线一致）、第四条（Trie 一次扫过命中 6 处），第五条是前四条全过。输出五条的结果。

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

提交你的答案

请登录后提交答案。

去登录

← 第四步多模式也要对账限时一秒的匹配靠什么过 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#include <algorithm>
#include <map>
#include <utility>

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

const vector<string> WORDS = {"he", "she", "his", "hers"};
const string TXT = "ushershishe";

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

struct TNode {
    map<char, TNode*> next;
    string word;          // 不空：有一个词在这里结束
};

TNode* build(const vector<string>& words) {
    TNode* root = new TNode();
    for (const string& w : words) {
        TNode* node = root;
        for (char ch : w) {
            if (!node->next.count(ch)) node->next[ch] = new TNode();
            node = node->next[ch];
        }
        node->word = w;
    }
    return root;
}

vector<pair<int, string>> scan(TNode* root, const string& txt) {
    vector<pair<int, string>> hits;
    for (int i = 0; i < (int)txt.size(); i++) {
        TNode* node = root;
        for (int j = i; j < (int)txt.size(); j++) {
            auto it = node->next.find(txt[j]);
            if (it == node->next.end()) break;
            node = it->second;
            if (!node->word.empty()) hits.push_back({i, node->word});
        }
    }
    sort(hits.begin(), hits.end());
    return hits;
}

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 && t.substr(i, p.size()) == p) out.push_back(i);
    }
    return out;
}

bool clause_kmp() {
    // TODO: KMP 的结果和暴力基准线完全一样
    return false;
}

bool clause_trie() {
    // TODO: Trie 一次扫过，命中正好 6 处
    return false;
}

int main() {
    vector<bool> c(5);
    c[0] = brute(T, P) == vector<int>({2, 7, 14});
    c[1] = by_hash(T, P) == brute(T, P);
    c[2] = clause_kmp();
    c[3] = clause_trie();
    c[4] = c[0] && c[1] && c[2] && c[3];
    for (int i = 0; i < 5; i++) cout << (i ? "/" : "") << (c[i] ? "过" : "不过");
    cout << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

交付五条验收一起过

更多题目

全部评论