題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1247

思路分析：題目要求找出在輸入字符串中的滿足要求（該字符串由輸入的字符串中的兩個字符串拼接而成）的字符串。

對于長度為LEN的字符串，其可能由LEN種可能的拼接可能；現在問題轉化為查找能夠拼接成該字符串的可能的兩個字符串是否都在

輸入的字符串中，使用字典樹可以實現快速的字符串查找，算法復雜度為O(N*M)，N為輸入字符串的個數，M為字符串長度。

?

代碼如下：

#include <cstdio> #include <cstring> #include <iostream> using namespace std;const int LEN = 100; const int MAX_N = 50000 + 10; const int KIND = 26; char str[MAX_N][LEN];struct Node {Node *next[KIND];bool end;Node(){memset(next, 0, sizeof(next));end = false;} };void Insert(Node *root, char *str) {int i = 0, k = 0;Node *p = root;while (str[i]) {k = str[i] - 'a';if (!p->next[k])p->next[k] = new Node();p = p->next[k];++i;}p->end = true; }bool Find(Node *root, char *str) {int i = 0, k = 0;Node *p = root;while (str[i]) {k = str[i] - 'a';p = p->next[k];if (!p)return false;++i;}return p->end; }int main() {int count = 0;Node *root = new Node();char sub_str1[LEN], sub_str2[LEN];while (scanf("%s", str[count]) != EOF)Insert(root, str[count++]);for (int i = 0; i < count; ++i) {int len = strlen(str[i]);for (int j = 1; j < len; ++j) {strncpy(sub_str1, str[i], j);sub_str1[j] = '\0';strncpy(sub_str2, str[i] + j, len - j);sub_str2[len - j] = '\0';if (Find(root, sub_str1) && Find(root, sub_str2)) {printf("%s\n", str[i]);break;}}}return 0; }

轉載于:https://www.cnblogs.com/tallisHe/p/4662634.html

總結

以上是生活随笔為你收集整理的hdoj 1247 Hat’s Words(字典树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。