字典树水题几枚

本文主要是介绍字典树水题几枚，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.HDU 1251 统计难题

很裸的一道字典树，直接输出个数的， 其实用map也能水过，只不过效率有些低

map版本

map做法就是把每个字符串的所有前缀遍历一遍，然后存起来，最后直接数个数就行。

具体代码吐下  很久很久以前的代码  很挫

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
char s[11];
int main()
{map<string,int>mp;int i;while(gets(s)){int len=strlen(s);if(!len)break;string a="";for(i=0;i<len;i++){a=a+s[i];mp[a]++;}}char ss[11];while(scanf("%s",ss)!=EOF){string tmp=ss;printf("%d\n",mp[tmp]);}return 0;
}

然后是字典树版本的， 刚写的，略挫

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define PI acos(-1.0)
using namespace std;
char str[12];
struct trie
{int num;trie *next[26];trie(){num = 0;for(int i = 0; i < 26; i++)next[i] = 0;}
} *root, temp[500005]; // 为了避免用new太多浪费时间，事先开好一个数组， 当然，内存又有可能爆掉了
int ncount = 0;
void insert(trie *p, char *s)
{int ix = 0;p ->num++;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ix++;}else{p -> next[nx] = &temp[ncount++]; //直接取址p = p -> next[nx];ix++;}p -> num++;}
}
int find(trie *p, char *s)
{int ix = 0, ans;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ans = p -> num;ix++;}else return 0;}return ans;
}
int main()
{//freopen("ride.in","r",stdin);//freopen("ride.out","w",stdout);root = new trie;while(gets(str)){if(strlen(str) == 0) break;insert(root, str);}while(scanf("%s", str) != EOF){printf("%d\n", find(root, str));}return 0;
}

 

2.POJ 2001 Shortest Prefixes

同样，很裸的字典树。

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define PI acos(-1.0)
using namespace std;
char s[1005][23];
struct trie
{int num;trie *next[26];trie(){num = 0;for(int i = 0; i < 26; i++)next[i] = NULL;}
}*root, temp[50000];
int ncount = 0;
void insert(trie *p, char *s)
{int ix = 0;p -> num++;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ix++;}else{p -> next[nx] = &temp[ncount++]; //直接取址p = p -> next[nx];ix++;}p -> num++;}
}
int find(trie *p, char *s)
{int ix = 0, ans;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ans = p -> num;ix++;}else return 0;}return ans;
}
int main()
{//freopen("ride.in","r",stdin);//freopen("ride.out","w",stdout);int cnt = 0, i, j;root = new trie;while(scanf("%s", s[cnt++]) != EOF){insert(root, s[cnt - 1]);}for(i = 0; i < cnt; i++){int len = strlen(s[i]);char tp[23];for(j = 0; j < 21; j++)tp[j] = '\0';int ct = 0;for(j = 0; j < len; j++){tp[ct++] = s[i][j];if(find(root, tp) == 1){break;}}printf("%s %s\n", s[i], tp);}return 0;
}

3. HDU 1247  

这个就当做模板吧。。。 

字典树应用，先插入所有单词，然后暴力拆分每个单词，看拆分后的两个单词是否都在字典树中出现，注意是确切出现，而不是作为子串出现，所以插入的时候注意下

/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define PI acos(-1.0)
using namespace std;
char str[50051][50];
struct trie
{int num;trie *next[26];trie(){num = 0;for(int i = 0; i < 26; i++)next[i] = NULL;}
} *root ;
int ncount = 0;
void insert(trie *p, char *s)
{int ix = 0;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx] == NULL)p -> next[nx] = new trie();p = p -> next[nx];ix++;}p -> num++;
}
int find(trie *p, char *s)
{int ix = 0, ans = 0;while(s[ix]){int nx = s[ix] - 'a';if(p -> next[nx]){p = p -> next[nx];ans = p -> num;ix++;}else return 0;}return ans;
}
int main()
{root = new trie();while(scanf("%s", str[ncount++]) != EOF){insert(root, str[ncount - 1]);}for(int i = 0; i < ncount; i++){int len = strlen(str[i]);int flag = 0;for(int j = 1; j < len; j++){char ta[22], tb[22];memset(ta, '\0', sizeof(ta));memset(tb, '\0', sizeof(tb));int cnt1 = 0, cnt2 = 0;for(int k = 0; k < j; k++)ta[cnt1++] = str[i][k];for(int k = j; k < len; k++)tb[cnt2++] = str[i][k];if(find(root, ta) && find(root, tb)){flag = 1;break;}}if(flag) puts(str[i]);}return 0;
}

这篇关于字典树水题几枚的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---