题目分析

我们需要实现一个搜索引擎，能够根据给定的查询条件从一组单词中找出符合条件的最小字典序单词。查询条件由多个术语（terms）组成，每个术语包含必须包含的字母（+）、必须排除的字母（-）和可选包含的字母（无符号）。一个单词只要满足任意一个术语的所有条件，就认为匹配成功。

解题思路

1. 输入处理：

   • 读取多个测试用例，每个测试用例包含一组单词和多个查询。
   • 单词列表以"*"结束，查询列表以"**"结束，整个输入以"#"结束。

2. 查询解析：

   • 每个查询由多个术语组成，术语之间用"|"分隔。
   • 每个术语包含：
     • 无符号字母：单词必须至少包含其中一个。
     • +字母：单词必须包含该字母。
     • -字母：单词不能包含该字母。

3. 匹配逻辑：

   • 对于每个查询，检查每个单词是否满足至少一个术语的所有条件。
   • 单词必须满足：
     • 至少包含术语中的一个无符号字母。
     • 包含所有+字母。
     • 不包含任何-字母。

4. 结果输出：

   • 对于每个查询，输出字典序最小的匹配单词，如果没有匹配则输出"NONE"。
   • 每个测试用例结束后输出"$"。

代码实现步骤

1. 输入处理：

   • 使用getline逐行读取输入，直到遇到"#"结束。
   • 对于每个测试用例，读取单词列表直到"*"，然后读取查询直到"**"。

2. 查询解析：

   • 将查询字符串按"|"分割为多个术语。
   • 对每个术语，解析出无符号字母、+字母和-字母。

3. 单词匹配：

   • 对每个单词，检查是否满足至少一个术语的所有条件。
   • 使用字符串查找功能检查字母的存在性。

4. 结果输出：

   • 对每个查询，遍历排序后的单词列表，找到第一个匹配的单词。
   • 如果没有匹配，输出"NONE"。

复杂度分析

• 时间复杂度：
  • 单词排序：O(N log N)，其中N是单词数量。
  • 每个查询处理：O(M × N × L)，其中M是术语数量，L是单词平均长度。
• 空间复杂度：
  • 存储单词和术语：O(N + M × K)，其中K是术语平均长度。

代码实现

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

struct Term {
    vector<char> unsigned_letters;
    vector<char> positive_letters;
    vector<char> negative_letters;
};

vector<string> words;
vector<vector<Term>> queries;

void process_test_case() {
    words.clear();
    queries.clear();
    string line;
    
    // Read words
    while (getline(cin, line) && line != "*") {
        words.push_back(line);
    }
    
    // Sort words lexicographically
    sort(words.begin(), words.end());
    
    // Read queries
    while (getline(cin, line) && line != "**") {
        vector<Term> query_terms;
        size_t pos = 0;
        string delimiter = "|";
        string token;
        
        // Split query into terms
        while ((pos = line.find(delimiter)) != string::npos) {
            token = line.substr(0, pos);
            
            Term term;
            for (size_t i = 0; i < token.size(); ) {
                if (token[i] == '+') {
                    term.positive_letters.push_back(token[i+1]);
                    i += 2;
                } else if (token[i] == '-') {
                    term.negative_letters.push_back(token[i+1]);
                    i += 2;
                } else {
                    term.unsigned_letters.push_back(token[i]);
                    i += 1;
                }
            }
            query_terms.push_back(term);
            line.erase(0, pos + delimiter.length());
        }
        
        // Process last term
        Term term;
        for (size_t i = 0; i < line.size(); ) {
            if (line[i] == '+') {
                term.positive_letters.push_back(line[i+1]);
                i += 2;
            } else if (line[i] == '-') {
                term.negative_letters.push_back(line[i+1]);
                i += 2;
            } else {
                term.unsigned_letters.push_back(line[i]);
                i += 1;
            }
        }
        query_terms.push_back(term);
        queries.push_back(query_terms);
    }
}

bool matches(const string& word, const Term& term) {
    // Check negative letters
    for (char c : term.negative_letters) {
        if (word.find(c) != string::npos) {
            return false;
        }
    }
    
    // Check positive letters
    for (char c : term.positive_letters) {
        if (word.find(c) == string::npos) {
            return false;
        }
    }
    
    // Check unsigned letters
    if (!term.unsigned_letters.empty()) {
        bool has_unsigned = false;
        for (char c : term.unsigned_letters) {
            if (word.find(c) != string::npos) {
                has_unsigned = true;
                break;
            }
        }
        if (!has_unsigned) {
            return false;
        }
    }
    
    return true;
}

void solve_query(const vector<Term>& query_terms) {
    for (const string& word : words) {
        for (const Term& term : query_terms) {
            if (matches(word, term)) {
                cout << word << endl;
                return;
            }
        }
    }
    cout << "NONE" << endl;
}

int main() {
    while (true) {
        string line;
        getline(cin, line);
        if (line == "#") break;
        
        // Put the first word back
        words.push_back(line);
        process_test_case();
        
        // Process queries
        for (const auto& query : queries) {
            solve_query(query);
        }
        
        cout << "$" << endl;
    }
    return 0;
}