P1770 万能的OIH搜索题解

OI_er · 2025-12-03 13:00:21 · 题解

有生之年竟然能交远古题的题解，写而无憾！

题目的描述太头疼了，我详细的说一下：

给你两个字符串 S_1 和 S_2，加粗（首尾分别添加 <b> 和 </b>）S_2 中在 S_1 出现的词语，希望加粗的数量尽可能少，而且每个标记之间的的字符数最少。标点符号加不加粗无所谓。

这里需要注意：标记之间的字符数是第一标准，其次是加粗的数量。也就是说，如果比较两个加粗处理后的句子，先看标记之间的字符，字符少的最优，如果相同，就看加粗的数量，数量少的最优。

比如拿样例的一部分来举例子：

shang wang ping an
ping an.  shang wang

这里如果这样标记：

<b>ping an</b>.  <b>shang wang</b>

字符间隔就不是最少的。

或者：

<b>ping an.<\b><b>  shang wang</b>

虽然标记之间的间隔少了，只有 0 字符，但是标记数不是最优的，所以应该像下面这样：

<b>ping an.  shang wang</b>

就是最优的了。

了解上面之后，我们有一个思路：

首先，将输入的字符串分解，变为单词和分隔符交替的序列，检测每个单词后的分隔符是否包含标点符号。有标点的单词不能作为词语的一部分。

然后，记录需要匹配的词语，匹配时忽略大小写，但输出时保持原样。

接着进行加粗，为了使加粗最优，将相邻的需要加粗的单词合并为一个加粗段，即使合并的单词之间有标点符号也包含在加粗段内。

最后，把每个连续加粗段都只用一对<b>和</b>标记。

代码实现（有注释）：

#include <bits/stdc++.h>
using namespace std;

struct W {
    string t, s;  // t:单词内容, s:单词后的分隔符
    bool p, b;     // p:分隔符中是否有标点, b:是否需要加粗
};

// 判断字符是否为字母
bool isL(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

// 判断字符是否为标点符号
bool isP(char c) {
    return !isL(c) && !isspace(c);
}

// 字符串转小写
string low(string x) {
    string r;
    for (char c : x) r += tolower(c);
    return r;
}

int main() {
    string k, t;
    getline(cin, k);
    getline(cin, t);

    vector<W> kw, tw;  // 关键词单词列表, 标题单词列表
    string tmp, sep;   // 临时存储当前单词和分隔符

    // 处理关键词
    for (char c : k) {
        if (isL(c)) {
            if (!sep.empty()) {
                if (!kw.empty()) kw.back().s = sep;
                sep.clear();
            }
            tmp += c;
        } else {
            if (!tmp.empty()) {
                kw.push_back({tmp, "", false, false});  // 存储单词
                tmp.clear();
            }
            sep += c;
        }
    }
    // 处理末尾的单词和分隔符
    if (!tmp.empty()) {
        kw.push_back({tmp, sep, false, false});
    } else if (!sep.empty() && !kw.empty()) {
        kw.back().s = sep;
    }

    // 分词处理标题
    tmp.clear();
    sep.clear();
    for (char c : t) {
        if (isL(c)) {
            if (!sep.empty()) {
                if (!tw.empty()) tw.back().s = sep;
                sep.clear();
            }
            tmp += c;
        } else {
            if (!tmp.empty()) {
                tw.push_back({tmp, "", false, false});
                tmp.clear();
            }
            sep += c;
        }
    }
    if (!tmp.empty()) {
        tw.push_back({tmp, sep, false, false});
    } else if (!sep.empty() && !tw.empty()) {
        tw.back().s = sep;
    }

    // 标记分隔符中是否有标点符号
    for (auto& w : kw)
        for (char c : w.s)
            if (isP(c)) {
                w.p = true;
                break;
            }

    for (auto& w : tw)
        for (char c : w.s)
            if (isP(c)) {
                w.p = true;
                break;
            }

    // 匹配词语
    for (int i = 0; i < (int)kw.size() - 1; i++) {
        if (kw[i].p) continue;  // 跳过有标点的单词
        for (int j = 0; j < (int)tw.size() - 1; j++) {
            if (tw[j].p) continue;  // 跳过有标点的单词
            // 检查是否匹配（不区分大小写）
            if (low(tw[j].t) == low(kw[i].t) && low(tw[j + 1].t) == low(kw[i + 1].t)) {
                tw[j].b = tw[j + 1].b = true;  // 标记需要加粗
            }
        }
    }
    bool inb = false;  // 当前是否在加粗段内
    for (int i = 0; i < tw.size(); i++) {
        if (tw[i].b) {
            if (!inb) {
                cout << "<b>";
                inb = true;
            }
            cout << tw[i].t;
            // 如果是最后一个单词或下一个单词不需要加粗，则结束加粗
            if (i == (int)tw.size() - 1 || !tw[i + 1].b) {
                cout << "</b>";
                inb = false;
            }
        } else {
            cout << tw[i].t;
        }
        cout << tw[i].s;
    }

    return 0;
}

P1770 万能的OIH搜索 题解

P1770 万能的OIH搜索题解