小记:A这题的过程是对字典树的一个进一步了解。确实让我理解的更深一刻了。因为在我有了一个自己的想法之后,我去校群里问了这个问题,回复给我的那个思想就是先将每个单词入树,然后对每个单词拆成两份,对每一份在Trie树立搜索,如果两份都能搜到,那么就代表这个单词是hat's word,输出。我那时觉得我自己的这个思想要好点,要快捷,但其实不然,在我想aa和a 这两个单词输入进去,输出会是什么的时候,我想清楚了,那就是在查找匹配的次数上我的想法所对比的次数要多。就是这点就说明了我对Trie树的了解还不是很足够,还有待加强,应用还不够灵活。再说一点就是这题用scanf读入和cin读入的差别有这么大,scanf要快很多。对于Trie树,用析构函数释放节点,比用递归释放是要快的,这个我试过了,而对于这题,不用释放也可以,但是运行内存会大几十K。题目中每个单词的长度不会超过26了,我居然测试出来了。好了,这题的小记就到这里了,每A一题对Trie树的了解应用就多了一点,还要加把劲,AC自动机还没开始A题啊。虽然早就看懂了,但是没有A过题的算法,不算会啊。
题解:没办法,分析清楚后还是拆分,听说这题map + string 来A 代码很短,没试过。
#include <string.h> #include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; #define MAX 26 typedef struct Node{ int isStr; struct Node *next[MAX]; Node():isStr(0){ memset(next, NULL, sizeof(next)); } ~Node(){ for(int i = 0;i < MAX; ++i) if(next[i] != NULL) delete next[i]; } }TrieNode,*Trie; Trie root; char s[50001][MAX]; void Insert(char *s){ TrieNode *p = root; while(*s){ if(p ->next[*s-'a'] == NULL){ p ->next[*s-'a'] = new TrieNode; } p = p ->next[*s-'a']; s++; } p->isStr = 1; return ; } int find(char *s){ TrieNode *p = root; while(*s){ if(p->next[*s - 'a'] != NULL){ p = p->next[*s - 'a']; s++; } else return 0; } return p->isStr; } int main() { //freopen("f:\\in1.txt","r",stdin); //freopen("f:\\out1.txt","w",stdout); int num = 0, k, i, j, flag, len; char s2[MAX]; root = new TrieNode; while(~scanf("%s",s[num])){ Insert(s[num++]); } for(i = 0; i < num; i ++){ flag = 0,len = strlen(s[i]); for(j = 0; j < len - 1; j ++){//len-1是因为你切西瓜一定要切在西瓜上。 for(k = 0; k <= j; k++){ s2[k] = s[i][k]; } s2[k] = '\0'; if(find(s2)){ strcpy(s2,s[i] + k); if(find(s2)){ puts(s[i]); break; } } } } delete root; }