一次扫过对比各扫一遍

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

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

两种做法都写好了。对一下结果，再把两种做法要看的字符数各算出来。

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

提交你的答案

请登录后提交答案。

去登录

← 哪个位置同时命中两个词回文子串和子序列哪个更难凑 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

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

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<pair<int, string>> one_by_one(const vector<string>& words, const string& txt) {
    vector<pair<int, string>> hits;
    for (const string& w : words) {
        for (int i = 0; i + (int)w.size() <= (int)txt.size(); i++) {
            if (txt.compare(i, w.size(), w) == 0) hits.push_back({i, w});
        }
    }
    sort(hits.begin(), hits.end());
    return hits;
}

int main() {
    auto a = scan(build(WORDS), TXT);
    auto b = one_by_one(WORDS, TXT);
    // TODO: 两种做法的命中必须完全一样，一样就是「一致」
    string verdict = "不一致";
    // TODO: 一次扫过要看 TXT.size() 个字符；各扫一遍要看 TXT.size() 乘词的个数
    int scan_once = -1, scan_each = -1;
    cout << a.size() << "/" << verdict << "/" << scan_once << "/" << scan_each << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

一次扫过对比各扫一遍

更多题目

全部评论