题目分析与解题方法

题目背景

本题目要求实现一个程序，用于检查一系列邮件中单词的拼写是否正确。具体来说：

1. 输入一组单词作为词典。
2. 对每个邮件输入一系列单词，判断这些单词是否在词典中。
3. 如果某个单词不在词典中，则记录错误，并列出所有未匹配的单词。

解题思路

数据结构设计

• 词典存储：使用二维字符数组 s[MAX][WORD_LEN] 来存储词典中的单词。
• 排序方式：利用 qsort 函数对词典进行快速排序，便于后续通过二分查找提高效率。
• 查找机制：通过自定义的二分查找函数 search 实现高效查找。

程序流程

1. 输入验证：
   • 验证词典数量 tot 是否在合理范围内。
   • 验证每个单词长度是否超过限定值 WORD_LEN。
2. 排序词典：
   • 使用 qsort 对词典按字典序排序。
3. 处理邮件：
   • 每次读取一个邮件，记录其编号。
   • 对邮件中的每个单词进行查找：
     • 若单词不在词典中，记录错误并列出未匹配单词。
     • 若所有单词均匹配，则标记邮件拼写正确。
4. 输出结果：
   • 最终输出每封邮件的拼写检查结果以及结束标志。

关键算法详解

快速排序 (qsort)

• 使用 qsort 对二维数组 s 进行排序，比较函数 cmp 基于 strcmp 实现。
• 时间复杂度为 $O(tot \cdot \log(tot))$。

二分查找 (search)

• 通过递归方式实现二分查找：
  • 初始区间为 [l, h]。
  • 计算中间位置 m = (l + h) / 2。
  • 比较目标值与中间值：
    • 若相等，返回索引 m。
    • 若小于中间值，调整右边界为 h = m - 1。
    • 若大于中间值，调整左边界为 l = m + 1。
• 时间复杂度为 $O(\log(tot))$。

示例运行

5
apple banana cat dog elephant
3
apple banana -1
cat dog tiger -1
elephant zebra -1

程序输出为：

Email 1 is spelled correctly.
Email 2 is not spelled correctly.
tiger
Email 3 is not spelled correctly.
zebra
End of Output

标程

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

const int MAX = 50000;
const int WORD_LEN = 200;
char s[MAX][WORD_LEN]; // 存储所有单词

// 比较函数，用于 qsort
int cmp(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

// 二分查找函数
int search(int l, int h, char *v) {
    int m;
    while (l < h) {
        m = (l + h) / 2;
        int res = strcmp(s[m], v);
        if (res == 0) return m;
        if (res < 0) l = m + 1;
        else h = m;
    }
    return -1;
}

int main() {
    int tot, n, k = 0;
    char a[WORD_LEN];

    // 输入单词集合
    cin >> tot;
    if (tot <= 0 || tot >= MAX) {
        cerr << "Error: Invalid number of words." << endl;
        return 1;
    }
    for (int i = 0; i < tot; i++) {
        cin >> s[i];
        if (strlen(s[i]) >= WORD_LEN) {
            cerr << "Error: Word too long at index " << i << "." << endl;
            return 1;
        }
    }

    // 对单词集合排序
    qsort(s, tot, sizeof(s[0]), cmp);

    // 输入查询次数
    cin >> n;
    if (n < 0 || n >= MAX) {
        cerr << "Error: Invalid number of queries." << endl;
        return 1;
    }
    
    while (n--) {
        bool flag = true;
        while (cin >> a && strcmp(a, "-1") != 0) {
            if (strlen(a) >= WORD_LEN) {
                cerr << "Error: Word too long in email input." << endl;
                return 1;
            }
            if (search(0, tot, a) == -1) {
                if (flag) {
                    flag = false;
                    cout << "Email " << ++k << " is not spelled correctly." << endl;
                }
                cout << a << endl;
            }
        }
        if (flag) {
            cout << "Email " << ++k << " is spelled correctly." << endl;
        }
    }

    cout << "End of Output" << endl;
    return 0;
}

总结

本题的核心在于高效地实现词典的构建与查找。通过排序和二分查找，可以显著提升查找效率，避免线性遍历带来的性能瓶颈。整个程序结构清晰，逻辑严谨，适合扩展至更复杂的拼写检查场景。