P1598. Excuses, Excuses! 题解（C++实现）

一、题目大意

给定一组关键词和多个借口，要求统计每个借口中关键词的出现次数（区分单词边界，不区分大小写），并输出出现次数最多的借口。关键词必须作为独立单词存在，被非字母字符、空格或行首尾分隔。

二、解题思路

核心逻辑

1. 单词边界识别：仅当关键词作为独立单词出现时才计数，例如dog出现在doghouse中不算匹配，但出现在my dog中算匹配。
2. 大小写无关匹配：将借口中的字母统一转为小写后与关键词对比。
3. 高效统计：遍历借口字符串，逐个字符拼接单词，遇到非字母字符时判断是否为关键词。

实现步骤

1. 输入处理：

   • 读取关键词数量K和借口数量E。
   • 读取K个关键词（均为小写，直接存储）。
   • 读取E个借口，每个借口可能包含大小写字母、标点和空格。

2. 单词分割与匹配：

   • 遍历借口的每个字符，拼接连续字母形成单词（转换为小写）。
   • 遇到非字母字符或字符串末尾时，判断当前单词是否为关键词（遍历关键词列表对比）。
   • 统计每个单词的匹配次数，累加得到每个借口的总匹配次数。

3. 结果筛选：

   • 找出匹配次数的最大值。
   • 输出所有匹配次数等于最大值的借口，保持输入顺序。

三、代码实现（C++）

#include <iostream>
#include <string>
#include <vector>
#include <cctype>
using namespace std;

// 处理单词：提取连续字母并转为小写
string processWord(const string& word) {
    string result;
    for (string::const_iterator it = word.begin(); it != word.end(); ++it) {
        if (isalpha(*it)) { // 仅处理字母字符
            result += tolower(*it); // 转小写
        } else {
            break; // 遇到非字母字符，停止处理（单词边界）
        }
    }
    return result;
}

// 统计借口中关键词出现次数
int countKeywordOccurrences(const string& excuse, const vector<string>& keywords) {
    int count = 0;
    string currentWord; // 临时存储当前单词
    for (size_t i = 0; i <= excuse.length(); ++i) { // 遍历到length处理末尾字符
        if (i < excuse.length() && isalpha(excuse[i])) { // 当前字符是字母
            currentWord += tolower(excuse[i]); // 转小写并拼接
        } else { // 非字母字符或字符串末尾
            if (!currentWord.empty()) { // 非空单词才匹配
                // 遍历关键词列表判断是否匹配
                for (vector<string>::const_iterator kwIt = keywords.begin(); kwIt != keywords.end(); ++kwIt) {
                    if (currentWord == *kwIt) {
                        count++; // 匹配一次
                    }
                }
                currentWord.clear(); // 清空当前单词，处理下一个单词
            }
        }
    }
    return count;
}

int main() {
    int K, E;
    int setNum = 1; // 测试用例编号
    while (cin >> K >> E) {
        cin.ignore(); // 忽略行末换行符（避免影响getline）
        
        // 读取关键词
        vector<string> keywords(K);
        for (int i = 0; i < K; ++i) {
            getline(cin, keywords[i]); // 关键词已为小写，直接存储
        }
        
        // 读取借口并统计次数
        vector<string> excuses(E);
        vector<int> counts(E, 0); // 存储每个借口的匹配次数
        int maxCount = 0; // 最大匹配次数
        for (int i = 0; i < E; ++i) {
            getline(cin, excuses[i]); // 读取完整借口（含空格、标点）
            counts[i] = countKeywordOccurrences(excuses[i], keywords); // 统计次数
            if (counts[i] > maxCount) {
                maxCount = counts[i]; // 更新最大值
            }
        }
        
        // 输出结果
        cout << "Excuse Set #" << setNum++ << endl;
        for (int i = 0; i < E; ++i) {
            if (counts[i] == maxCount) {
                cout << excuses[i] << endl; // 输出符合条件的借口
            }
        }
        cout << endl; // 每组数据后输出空行
    }
    return 0;
}

四、代码解析

1. processWord 函数：

   • 功能：从字符串中提取连续字母，转为小写，遇到非字母字符立即停止（确保单词边界正确）。
   • 实现：使用迭代器遍历字符串，逐个字符判断是否为字母，非字母时终止处理。

2. countKeywordOccurrences 函数：

   • 功能：遍历借口字符串，分割单词并统计关键词匹配次数。
   • 实现：
     • 逐个字符拼接字母形成单词（转小写）。
     • 遇到非字母字符或字符串末尾时，遍历关键词列表判断是否匹配，匹配则计数加一。

3. 主函数：

   • 输入处理：使用getline读取关键词和借口，避免空格影响。
   • 结果统计：记录每个借口的匹配次数，找出最大值并输出所有符合条件的借口。
   • 格式控制：每组数据后输出空行，符合题目要求。

五、注意事项

1. 单词边界处理：非字母字符（如空格、标点）作为单词分隔符，确保关键词仅作为独立单词匹配。
2. 大小写转换：统一转为小写后对比，避免因大小写不同导致的匹配失败。
3. 输入流处理：使用cin.ignore()清除行末换行符，防止getline读取空行。

通过以上方法，代码能够准确识别单词边界，高效统计关键词出现次数，满足题目要求。