hdu1251 && hud 1247 （字典树）

hdu1251 题目

这道题，主要是在主函数的输入输出上犹豫了。

#include<stdio.h> #include<cstring> #include<iostream> using namespace std; #include<algorithm> const int Max = 1e6+5; struct Trie{ Trie * next[26]; int cnt; }; int malloc_p=0; Trie memory[Max]; Trie *creat() { Trie * t = &memory[malloc_p++]; t->cnt=1; for(int i=0;i<26;i++) t->next[i]=NULL; return t; } void _insert(Trie *root,char* str) { Trie* p=root; for(int i=0;str[i]!='\0';i++) { int k=str[i]-'a'; if(p->next[k]) p->next[k]->cnt++; else p->next[k]=creat(); p=p->next[k]; } } int _search(Trie *root ,char* str) { Trie *p = root; for(int i=0;str[i]!=0;i++) { int k = str[i]-'a'; if(p->next[k]) p=p->next[k]; else return 0; } return p->cnt; } int main() { char str[15]; Trie *root = creat(); while(gets(str)&&strlen(str)!=0){ _insert(root,str);} while(cin>>str){ int ans=_search(root,str); printf("%d\n",ans); } return 0; }

hdu1247 题目

题目大意：

就是找出一个单词，前半部是一个出现过的单词，后半部也是，记住，要严格满足这个条件

所以，其实也就是先查找一个单词的是否有前缀，再用这个单词除去前缀的部分查找是否存在一个这样的单词

虽然题目说按字典序输出，但本身已经是按字典序输入了，所以排序也就省了

#include<stdio.h> #include<cstring> #include<iostream> using namespace std; #include<algorithm> struct Trie{ Trie * next[26]; int cnt; }; Trie *root; int malloc_p=0; char str[50004][14]; void _insert(char* s) { Trie* p=root; for(int i=0;s[i]!='\0';i++) { int k=s[i]-'a'; if(p->next[k]==NULL) p->next[k]=new Trie(); p=p->next[k]; } p->cnt=1; } int _search2(char* s) { Trie *p = root; for(int i=0;s[i]!='\0';i++) { int k = s[i]-'a'; if(p->next[k]) { p=p->next[k]; if(p->cnt==1&&s[i+1]=='\0')// return 1; } else return 0; } return 0; } int _search(char* s) { Trie *p = root; for(;*s!='\0';) { int k = *s-'a'; if(p->next[k]) { p=p->next[k]; if(p->cnt==1&& _search2(s+1) )// return 1; s++; } else return 0; } return 0; } int main() { int i=0; root = new Trie(); while(cin>>str[i]){ _insert(str[i]); i++; } for(int j=0;j<i;j++){ if(_search(str[j])) cout<<str[j]<<endl; } return 0; } 博客上很多人说这道题挺简单的，但是我还是做了好长时间，可能是因为才开始接触字典树，还不太熟悉吧，

下面是转载的别人的代码：map+string

感觉挺简单的，但是现在还没有学map ,以后应该看得懂吧

#include <iostream>   #include <string>   #include <map>      using namespace std;      map <string, int> m_v;      string str[50006];      int main() {       int k(-1);       while(cin >> str[++k]) {           m_v[str[k]] = 1;       }       for(int i = 0; i <= k; i++) {           int e = str[i].size()-1;           for(int j = 1; j < e; j++) {               string s1(str[i], 0, j);               string s2(str[i], j);               if(m_v[s1] == 1 && m_v[s2] == 1) {                   cout << str[i] << endl;                   break;               }           }       }       return 0;   }