寻找克隆人(Find The Clones) Trie字典树

前言

  作为一名合格的美工,当然每天画图做图是必须的,所以下面这一题就很好的体现了我们美工的精湛技艺,好了,废话不多说,直接上甲方要求。

题目

Find the Clones

  Doubleville, a small town in Texas, was attacked by the aliens. They have abducted some of the residents and taken them to the a spaceship orbiting around earth. After some (quite unpleasant) human experiments, the aliens cloned the victims, and released multiple copies of them back in Doubleville. So now it might happen that there are 6 identical person named Hugh F. Bumblebee: the original person and its 5 copies. The Federal Bureau of Unauthorized Cloning (FBUC) charged you with the task of determining how many copies were made from each person. To help you in your task, FBUC have collected a DNA sample from each person. All copies of the same person have the same DNA sequence, and different people have different sequences (we know that there are no identical twins in the town, this is not an issue).

Input

  The input contains several blocks of test cases. Each case begins with a line containing two integers: the number 1 ≤ n ≤ 20000 people, and the length 1 ≤ m ≤ 20 of the DNA sequences. The next n lines contain the DNA sequences: each line contains a sequence of m characters, where each character is either "A", "C", "G" or "T'".
The input is terminated by a block with n = m = 0 .

Output

  For each test case, you have to output n lines, each line containing a single integer. The first line contains the number of different people that were not copied. The second line contains the number of people that were copied only once (i.e., there are two identical copies for each such person.) The third line contains the number of people that are present in three identical copies, and so on: the i -th line contains the number of persons that are present in i identical copies. For example, if there are 11 samples, one of them is from John Smith, and all the others are from copies of Joe Foobar, then you have to print "1" in the first andthe tenth lines, and "0" in all the other lines.

Sample Input

9 6
AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC
0 0

Sample Output

1
2
0
1
0
0
0
0
0

Hint

  Huge input file, 'scanf' recommended to avoid TLE.

假装题解

  这题大概意思就是给你n(人数)、m(DNA长度),然后整理克隆人的信息,输出从0个克隆人到n个克隆人,每种有多少个。那么对于这种题目,我们究竟该怎么画图呢?

Trie字典树

  如图所示,我们使用Trie字典树存储我们的数据,默认状态下,每个节点End=falsesame=0。这样每次添加我们的DNA至最后节点时,same++。所以核心结构就这样介绍完了。那么接下来只要向这颗Trie字典树里添加节点就好了。

  我们使用二维数组来存储我们的DNA结构,一维存储首字母,然后二维存储接下来的DNA序列。美工CongTsang又要继续做图了。如下图所示:

DNA存储

  这样我们输入一组DNA时,就保存好了她的结构,之后传入函数就可以一个一个读取其中的信息。(ps:虽然我研究了蛮久的,不过还是蛮好的)那么到此题解就差不多结束了。核心已经吹完了。学没学到就靠自己了,留言也是可以的。

假装源码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20005;
const int M = 25;

char DNA[N][M];
int ans[N];
int deep; // 除去跟节点的深度

struct node
{
    node *next[4];
    int same;
    bool End;
} Tree [N*M];

void init(node *p)
{
    memset(p->next, NULL, sizeof(p->next));
    p->same=0;
    p->End=false;
}

int translation(char a)
{
    if (a == 'A')
        return 0;
    if (a == 'C')
        return 1;
    if (a == 'G')
        return 2;
    if (a == 'T')
        return 3;
    return -1;
}

void insertNode(node *p, char *dna)
{
    for (int i = 0; dna[i] != '\0'; i++)// 二维打击
    {
        int index = translation(dna[i]);
        if (p->next[index] == NULL)
        {
            deep++;
            p->next[index] = Tree + deep;
            init(p->next[index]);
        }
        p = p->next[index];
    }
    if (p->End)
    {
        p->same++;
        return;
    }
    p->End = true;
    p->same++;
    return;
}


int main()
{
    int n,m;
    while (cin>>n>>m && (n + m))
    {
        node *root = Tree;
        init(root);
        deep = 0;
        memset(ans, 0 ,sizeof(ans));

        for (int i = 0; i < n; i++)
        {
            cin>>DNA[i];// 输入一组DNA
            insertNode(root, DNA[i]);// 进入二维盗梦空间
        }
        for (int i = 1; i <= deep; i++)
        {
            if (Tree[i].End)
            {
                ans[Tree[i].same]++;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            cout<<ans[i]<<endl;
        }
    }

    return 0;
}

题源

  POJ这是提交入口,请尊重自己的学习。


爱狂笑的孩子运气不会差