【PTA数据结构 | C语言版】前缀树的3个操作

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请编写程序，利用前缀树查找给定字符串是否在某给定字符串集合 S 中。

输入格式：
输入首先给出一个正整数 n（≤1000），随后 n 行，每行给出一个仅由小写英文字母组成、长度不超过 1000 的字符串，以回车结尾。以上为给定字符串集合 S。
接下来给出查询请求。首先给出一个正整数 m（≤1000），随后 m 行，每行给出一个仅由小写英文字母组成、长度不超过 1000 的待查找字符串，以回车结尾。

输出格式：
对每个待查找的字符串，如果它在 S 中，则在一行中输出 yes；否则输出 no。

输入样例：
3
binarytree
trie
binarysearch
5
binary
trie
tree
binarytree
binarysearch

输出样例：
no
yes
no
yes
yes

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 10000
#define MAX_LENGTH 10001

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

// 二分查找函数
int binary_search(const char **arr, int n, const char *target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = strcmp(arr[mid], target);
        if (cmp == 0) {
            return 1; // 找到目标字符串
        } else if (cmp < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return 0; // 未找到目标字符串
}

int main() {
    int n, m;
    char **S = (char **)malloc(MAX_N * sizeof(char *));

    // 读取集合 S
    scanf("%d", &n);
    getchar(); // 消耗掉scanf后的换行符
    for (int i = 0; i < n; i++) {
        S[i] = (char *)malloc(MAX_LENGTH * sizeof(char));
        fgets(S[i], MAX_LENGTH, stdin);
        // 移除换行符
        size_t len = strlen(S[i]);
        if (len > 0 && S[i][len - 1] == '\n') {
            S[i][len - 1] = '\0';
        }
    }

    // 对集合 S 进行排序，以便使用二分查找
    qsort(S, n, sizeof(char *), compare);

    // 处理查询
    scanf("%d", &m);
    getchar(); // 消耗掉scanf后的换行符
    for (int i = 0; i < m; i++) {
        char query[MAX_LENGTH];
        fgets(query, MAX_LENGTH, stdin);
        // 移除换行符
        size_t len = strlen(query);
        if (len > 0 && query[len - 1] == '\n') {
            query[len - 1] = '\0';
        }

        // 使用二分查找判断查询字符串是否存在于集合 S 中
        if (binary_search(S, n, query)) {
            printf("yes\n");
        } else {
            printf("no\n");
        }
    }

    return 0;
}