动态建树之——出现了几次的单词有几个

题目：poj2945

题意：计算出现了1~n次的单词各有几次

解答：字典树。建立之后dfs查找

注意：mle:树的节点数目定义太大了。因为题目只有ACGT四个字母所以节点数定义为4就足够

            map定义啥的不能写在函数外面

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> using namespace std; const int MAXN = 20020; int ans[MAXN]; int m; const int sonnum = 4,base = 'A'; int arr[4] = {0,2,6,19}; struct Trie { int num; bool terminal; struct Trie *son[sonnum]; }; Trie *NewTrie() { Trie *temp = new Trie; temp -> num = 1; temp -> terminal = false; for(int i = 0;i < sonnum;i++) temp -> son[i] = NULL; return temp; } void Insert(Trie *pnt,char *s,int len) { map<int,int> Map; Map[0] = 0; Map[2] = 1; Map[6] = 2; Map[19] = 3; Trie *temp = pnt; for(int i = 0;i < len;i++) { if(temp -> son[Map[s[i]-base]] == NULL) { temp -> son[Map[s[i]-base]] = NewTrie(); } else temp -> son[Map[s[i]-base]] -> num++; temp = temp -> son[Map[s[i]-base]]; } temp -> terminal = true; return; } void dfs(Trie *pnt,int step) { if(step == m) { if(pnt -> terminal == true) ans[pnt -> num]++; return; } for(int i = 0;i < 4;i++) { Trie *temp = pnt; if(temp -> son[i] != NULL) dfs(temp -> son[i],step + 1); } return; } int main() { int n; char a[25]; while(~scanf("%d%d",&n,&m)) { if(n == 0 && m == 0) break; Trie *tree = NewTrie(); memset(ans,0,sizeof(ans)); for(int i = 0;i < n;i++) { scanf("%s",a); Insert(tree,a,m); } dfs(tree,0); for(int i = 1;i <= n;i++) printf("%d\n",ans[i]); } return 0; }