用链式字典树解决POJ2945

首先，我们的思路是用链式的字典树结构，解决poj2945这道题

题意是，统计所有的字符串出现的次数，并依次输出各个次数的数量

例如:

input

9 6
AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC

out

遇到的一些小麻烦 : 之前提交poj爆内存了,就试了一下这个代码，结果还是爆内存，后来发现，我这里不能设置位 Node *next[26],不然铁定爆内存，于是我认真审题，发现这里设置为4就好啦因为只有4个字符需要入树，至于怎么判断下标，我们用一个fun()函数来解决就好了。
具体的思路就是 : 先用find()判断，是否在树里有该个DNA,如果有让，count[i]--,i++,;count[i]++,   如果没有，用T_insert插入,并给count[1]置为1；
最后输出for(i::n)printf("%d\n",count[i]);就可以了。

 #include <iostream>

 #include <cstdio>

 #pragma comment(linker, "/STACK:1024000000,1024000000")　　　　

 #include <cstring>

 using namespace std;

 struct Node

 {

     Node *next[];　　　　　

     char val;　　　　　　　　　　

     int count;

     Node(char val)

     {

         this->val =val;

         count=;

         memset(next,NULL,sizeof(next));

     }

 };

 Node *root =new Node('\0');

 int *count;

 //int *count;

 int   fun(char s)

 {

     switch(s)

     {

         case 'A':return ;break;

         case 'C':return ;break;

         case 'G':return ;break;

         case 'T':return ;break;

     }

 }

 bool T_Find(char *s)

 {

     int len=strlen(s);

     Node *p=root;

     for(int i=;i<len;i++)

     {

         int pos=fun(s[i]);

         if(p->next[pos]==NULL)

             return false;

         p=p->next[pos];

     }

     count[p->count]--;      //如果 程序运行到最后，出现过两次了，那么 p->count 出现过一次的 count[p->count] -- ,也就是给出现一次的次数减一

     p->count++;             //然后给   p->count 置为出现过2 次

     count[p->count]++;

     return true;

 }

 void T_insert(char *s)

 {

     int len=strlen(s);

     Node *p=root;

     for(int i=;i<len;i++)

     {

         int pos=fun(s[i]);

         if(p->next[pos]==NULL)

         {

             p->next[pos]= new Node(s[i]);

         }

         p=p->next[pos];

     }

     p->count=;

     count[p->count]++;

 }

 /*

 9 6

 AAAAAA

 ACACAC

 GTTTTG

 ACACAC

 GTTTTG

 ACACAC

 ACACAC

 TCCCCC

 TCCCCC

 0 0

 */

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)==&&n&&m)

     {

         count =new int [n+];

         fill(count,count+n+,);

         for(int i=;i<n;i++)

         {

             char *s;

             s= new char[m+];

             scanf("%s",s);

             if(T_Find(s)==false)

             {

                 T_insert(s);

             }

         }

         int i=;

         for( i=;i<=n;i++)

         {

             printf("%d\n",count[i]);

         }

     }

     return ;

 }

巴特西

用链式字典树解决POJ2945

最新文章

热门文章