题意:按字典序输入一系列单词,输入结束后,判断哪些单词是由其余两个单词连接而成。若是,则输出(输出也按字典序)。
#include <iostream> using namespace std; char list[50001][26]; const int kind = 26; int cnt = 0; struct Treenode { bool flag; Treenode *next[kind]; Treenode() { flag = false; for ( int i = 0; i < kind; ++i ) next[i] = NULL; } } node[100000]; void Insert ( Treenode *&root, char *word ) { Treenode *location = root; if ( location == NULL ) { location = &node[cnt++]; root = location; } int id, i = 0; while ( word[i] ) { id = word[i] - 'a'; if ( location->next[id] == NULL ) location->next[id] = &node[cnt++]; location = location->next[id]; ++i; } location->flag = true; /*注意标记单词的最后一个字母,说明在这之前的字母组成一个单词,以便查询时划分*/ } bool check ( Treenode *root, char* word ) { Treenode *location = root; if ( location == NULL ) return false; int id, i = 0, len = strlen(word); while ( word[i] ) { id = word[i] - 'a'; if ( location->next[id] == NULL ) return false; if ( i == len-1 && location->next[id]->flag == true ) return true;/*查找到最后一个字符时,节点的标记应该是true,这样才是完全匹配的*/ location = location->next[id]; ++i; } return false; } bool Search ( Treenode *root, char * word ) { Treenode *location = root; if ( location == NULL ) return false; int id, i = 0, len = strlen(word); while ( word[i] ) { id = word[i] - 'a'; if ( location->next[id] == NULL ) return false; if ( location->next[id]->flag == true )/*当检测到一个标记时说明单词的前半部分已经检测到,现在只需检测后面一部分是否能由另一个单词构成*/ { if ( i + 1 < len && check(root,&word[i+1]) ) return true; } location = location->next[id]; ++i; } return false; } int main() { int i = 0, j; Treenode *root = NULL; while ( scanf("%s", list[i]) != EOF ) { Insert(root,list[i]); ++i; } for ( j = 0; j < i; ++j ) { if ( Search(root,list[j]) ) printf("%s\n",list[j]); } return 0; }