题目链接：Hat’s Words
题目大意：给定一些单词组成一个字典，判断每个单词是否能由字典中的词组成
分析：50000个单词，假设长度为len，如果暴力的话每个单词需要比较len*50000^2次，肯定会超时；
如果用字典树，建树O(n*len)，查询每个单词只需要O（len）
对每个单词，划分为(1,2...i,)和(i+1....len)若恰好能找到则输出
注意，每个单词只能输出一次，即如果ahat能分成a\hat和aha\t，只输出一个ahat
#pragma warning(disable:4996) #include <stdio.h> #include <string.h> #include <stdlib.h> const int maxn = 26; const int maxw = 50005; struct node { node *next[maxn]; int v; }; char str[maxw][105]; node *root; void creatTrie() { root = (node *)malloc(sizeof(node)); for (int i = 0; i<maxn; i++)root->next[i] = NULL; } void Insert(char *str) { int len = strlen(str); node *p = root, *q; for (int i = 0; i<len; i++){ int id = str[i] - 'a'; if (p->next[id] == NULL){ q = (node*)malloc(sizeof(node)); for (int j = 0; j<maxn; j++)q->next[j] = NULL; q->v = 1; p->next[id] = q; p = p->next[id]; } else{ p = p->next[id]; } } p->v = -1;//单词末尾为-1 } bool Find2(char *str) { int len = strlen(str); node *p = root; for (int i = 0; i<len; i++){ int id = str[i] - 'a'; p = p->next[id]; if (p == NULL)return false; if (p->v == -1 && i == len - 1)return true;//是一个单词且干好到达str的末尾 } return false; } bool Find(char *str) { int len = strlen(str); node *p = root; for (int i = 0; i<len; i++){ int id = str[i] - 'a'; p = p->next[id]; if (p == NULL)return false; else if (p->v == -1 && Find2(str + i + 1))return true;//前缀是一个单词，且剩下的部分也是一个单词 } return false; } int main() { //freopen("in.txt", "r", stdin); int tot = 0; creatTrie(); while (scanf("%s", str[tot]) != EOF){ Insert(str[tot]); tot++; } for (int i = 0; i<tot; i++){ if (Find(str[i]))printf("%s\n", str[i]); } return 0; }
map做法
#include <iostream> #include <string> #include <set> #include <stdio.h> using namespace std; int main() { freopen("in.txt","r",stdin); set<string>Set; string s;//,s1,s2; while(cin>>s){ Set.insert(s); for(set<string>::iterator it;it!=Set.end();++it){ s=*it; for(int i=0;i<s.size();i++){ //s1.assign(s,0,j); // s2.assign(s,j,s.size()-j); string s1 ( s, 0, j );//0开始长度为j string s2 ( s, j );//初始位置在j if(Set.find(s1)&&Set.find(s2))cout<<s<<endl; } } } return 0; }
