HDU 1251(字典树)

以你之姓@ 2022-09-20 12:35 112阅读 0赞

题意：如题。

#include <iostream>
    #include <string>
    #include <cstring>
    #include <sstream>
    using namespace std;
    
    struct Trie
    {
        int count;
        Trie* next[26];
        Trie() : count(0) { memset(next, 0, sizeof (next)); }
    };
    
    void insert(Trie* root, string& s, int len)
    {
        Trie* p = root;
        int i;
        if (p == NULL)
            p = new Trie;
        p->count++;
        for (i = 0; i < len; ++i)
        {
            if (p->next[s[i] - 'a'] == NULL)
                p->next[s[i] - 'a'] = new Trie;
            p = p->next[s[i] - 'a'];
            p->count++;
        }
    }
    
    int search(Trie* root, string& s, int len)
    {
        Trie* p = root;
        int i;
        if (p == NULL)
            return 0;
        for (i = 0; i < len; ++i)
        {
            if (p->next[s[i] - 'a'] == NULL)
                return 0;
            p = p->next[s[i] - 'a'];
        }
        return p->count;
    }
    
    void freeTrie(Trie* root)
    {
        if (root == NULL)
            return;
        for (int i = 0; i < 26; ++i)
            if (root->next[i] != NULL)
                freeTrie(root->next[i]);
        delete root;
    }
    
    int main()
    {
        Trie* root = new Trie;
        string line;
        int len;
        while (getline(cin, line), (len = line.length()))
            insert(root, line, len);
        while (getline(cin, line))
            cout << search(root, line, line.length()) << endl;
        freeTrie(root);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关统计难题 HDU - 1251（字典树）

统计难题 HDU - 1251 题目链接：[https://vjudge.net/problem/HDU-1251][https_vjudge.net_problem_H

旧城等待，/ 2023年08月17日 15:41/ 0 赞/ 76 阅读

相关 HDU 1251 统计难题（字典树模板）

<table style="font-family:"Times New Roman"; word-wrap:break-word"> <tbody>

川长思鸟来/ 2022年09月28日 13:24/ 0 赞/ 142 阅读

相关 HDU 1251(字典树)

题意：如题。 include <iostream> include <string> include <cstring> incl

以你之姓@/ 2022年09月20日 12:35/ 0 赞/ 113 阅读

相关 Trie字典树应用HDU--1251

[HDU--1251题统计难题][HDU--1251_] 这个题用到了字典树。这个知识点是栋栋哥上个星期五讲的，其他几个人也都做过这方面的练习，我直到昨天下午才弄字

素颜马尾好姑娘i/ 2022年08月26日 14:24/ 0 赞/ 136 阅读

相关 HDU 1251-统计难题（字典树-统计前缀串）

统计难题 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others

ゝ一世哀愁。/ 2022年08月21日 13:47/ 0 赞/ 123 阅读

相关字典树之统计难题 hdu1251

这一题本来打算存到一个字符串的数组里，到输入要查找的前缀后再去查找；结果去实现时发现如果要提前给的单词非常多的话每次查找都是比较慢的;交上去果断TLE.... 即使用了快排，

川长思鸟来/ 2022年08月10日 15:55/ 0 赞/ 142 阅读

相关 hdu 1251 简单字典树

统计难题 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Oth

古城微笑少年丶/ 2022年08月05日 11:22/ 0 赞/ 98 阅读

相关 HDOJ 1251-统计难题【模板：字典树】

统计难题 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others

深碍√TFBOYSˉ_/ 2022年07月24日 05:21/ 0 赞/ 174 阅读

相关 HDU - 1251 统计难题（字典树）

统计难题 Problem Description Ignatius最近遇到

迷南。/ 2022年05月16日 01:29/ 0 赞/ 148 阅读

相关 HDU -1251 统计难题【字典树】题解

目录 1.题目 2.代码 1.题目 Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,

我会带着你远行/ 2021年07月24日 19:34/ 0 赞/ 306 阅读