本文共 1626 字,大约阅读时间需要 5 分钟。
Hat’s Words(hdu 1247)
一个 “hat’s word”是一个单词可以恰好由字典中其他两个单词联接得到。给出你字典中的单词,你的工作是找出字典中所有的hat’s word。
输入:
每行为一个单词,由小写英文字母组成。所有单词按照字典顺序排列,总数不超过50,000。只有一组测试数据。
输出:
输出为所有的hat’s word,且按照字典顺序输出。
输入样例:
a
ahat
hat
hatword
hziee
word
输出样例:
ahat
hatword
分析:
将每个单词都插入到Trie树里,并按顺序依次判断每个单词是不是hat’s word。判断一个单词是不是hat’s word时,用暴力将这个单词分成前后两部分,判断这两部分是否都出现在Trie树里。
代码:
#include#include #include #include using namespace std;char ch[50050][100];struct node{ struct node * next[26]; bool value; node() { for(int i = 0; i < 26; i++) next[i] = NULL; value = false; }}* root;void insert(char s[]){ int k = 0; node *p = root; while(s[k] != '\0') { if( ! p->next[s[k]-'a']) p->next[s[k]-'a'] = new node(); p = p->next[s[k]-'a']; k++; } p->value = true;}bool find(char s[]){ int k = 0; node *p = root; while(s[k] != '\0' && p->next[s[k]-'a']) { p = p->next[s[k]-'a']; k++; } if(s[k] == '\0' && p->value) return p->value; return false;}int main(){ int i = 0, k; root = new node(); while(scanf("%s", ch[i]) != EOF) { insert(ch[i]); i++; } for(k = 0; k < i; k++) { int j; for(j = 1;j < strlen(ch[k]) - 1; j++) { char s1[100], s2[100]; for(int jj = 0; jj < j; jj++) s1[jj] = ch[k][jj]; s1[j] = '\0'; strcpy(s2, ch[k] + j); if(find(s1) && find(s2)) { cout << ch[k] << "\n"; break; } } } return 0;}
转载地址:http://zpali.baihongyu.com/