首页 > 代码库 > POJ 290 动物排序加强版

POJ 290 动物排序加强版

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=290

 

思路: 字典树。

 

#include <iostream>#include <malloc.h>#include <cstdio>#include <cstring>using namespace std;struct tirenode{    int num;    struct tirenode * b[26];}tire;  void init(){    for(int i = 0; i < 26; i++)        tire.b[i] = NULL;}int insert(char data[10]){    int i;    int len = strlen(data);        struct tirenode * temp = &tire;        for(i = 0; i < len; i++)    {            if(temp->b[data[i] - a] == NULL)        {            temp->b[data[i] - a] = (struct tirenode *)malloc( sizeof(struct tirenode) );            for(int j = 0; j < 26; j++)                temp ->b[data[i] - a] -> b[j] = NULL;            if(i == len-1)            {                temp ->b[data[i] - a] -> num = 1;                return temp ->b[data[i] - a] -> num;            }            else            {                temp ->b[data[i] - a] -> num = 0;             }        }        else        {            if(i == len-1)            {                temp ->b[data[i] - a] -> num++;                return temp ->b[data[i] - a] -> num;            }        }        temp = temp->b[data[i] - a];    }}int main(){    int n;    scanf("%d", &n);    char c[10];    int max = 0;    char res[10];    int num = 0;        init();        for(int i = 0; i < n; i++)    {        scanf("%s",c);        num = insert(c);        if( max < num )        {            max = num;            strcpy(res,c);        }    }        printf("%s %d\n",res,max);     return 0;} 

 

POJ 290 动物排序加强版