本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

請編寫程序，利用前綴樹查找給定字符串是否在某給定字符串集合 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 *));// 讀取集合 Sscanf("%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;
}