首页 > 代码库 > POJ - 2418 代码

POJ - 2418 代码

2024-07-13 22:35:33   220人阅读

使用Trie树完成。比STL map 快很多。

输出时DFS，用一个字符数组记录当前字符串。

走到是字符串的结点就输出。

 

代码如下。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <cstdlib>using namespace std;const int MaxL = 30 + 3, MaxNext = 256 + 5, MaxNode = 1000000 + 5;char Str[MaxL];int tot = 0, top = 0;typedef struct TrieNode{    int num;    bool isStr;    TrieNode *Next[MaxNext];} Trie;Trie *root, Ta[MaxNode];void Insert(Trie *root, char *S, int len){    if (root == NULL || len == 0) return;    Trie *p = root;    for (int i = 0; i <= len - 1; i++)    {        if (p -> Next[S[i]] == NULL)        {            Trie *temp = &Ta[++top];            temp -> isStr = false;            temp -> num = 0;            for (int j = 0; j <= 256; j++) temp -> Next[j] = NULL;            p -> Next[S[i]] = temp;        }        p = p -> Next[S[i]];    }    p -> isStr = true;    p -> num++;}int l; void Output_Str(Trie *root, int l){    if (root -> isStr == true)     {        for (int i = 0; i <= l + 1 - 1; i++) printf("%c", Str[i]);        printf(" %.4lf\n", (root -> num) * 100.0 / tot);    }    Trie *p = root;    for (int i = 0; i <= 256; i++)    {        if (p -> Next[i] != NULL)         {            Str[l + 1 + 1 - 1] = i;            Output_Str(p -> Next[i], l + 1);        }    }}int main(){    root = &Ta[++top];    root -> isStr = false;    for (int i = 0; i <= 256; i++) root -> Next[i] = NULL;    root -> num = 0;    while (gets(Str))    {        Insert(root, Str, strlen(Str));        tot++;    }    Output_Str(root, -1);    return 0;}


联系
我们