专栏首页用户6093955的专栏【统计难题】【HDU - 1251】【map打表或字典树】【字典树模板】

【统计难题】【HDU - 1251】【map打表或字典树】【字典树模板】

思路

题意题目为中文题,这里不再过多阐述。 思路1:可以在读入单词表的过程中将单词分解,用map将它一 一记录 思路2:利用字典树,这个方法较快些,下面代码中会分别给出数组和结构体指针两种形式的字典树,指针形式的有时可能会因题目内存限制而导致Memory Limit Exceeded,这时就可选择数组形式的。不过对于本题来说不用担心。

AC代码

代码1:map打表

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
map<string, int> table;
int main()
{
    std::ios::sync_with_stdio(false);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    table.clear();
    string s;
    while(getline(cin, s))
    {
        if(s[0] == '\0')
            break;
        string ss = "";
        for(int i = 0; i < s.size(); i++)
        {
            ss += s[i];
            table[ss]++;
        }
    }
    while(cin >> s)
    {
        cout << table[s] << endl;
    }
}

代码2:数组形式的字典树

#include<bits/stdc++.h>
using namespace std;
const int maxnode = 400001;
const int maxs = 27;
char s[10 + 10];
int trie[maxnode][maxs] ;
int sum[maxnode] ;
int node = 0;
void inserts(char *t)
{
    int len = strlen(t);
    int cur = 0;
    for(int i = 0; i < len; i++)
    {
        int p = t[i] - 'a';
        if(!trie[cur][p])
            trie[cur][p] = ++node;
        sum[trie[cur][p]]++;
        cur = trie[cur][p];
    }
}
int searchs(char *t)
{
    int len = strlen(t);
    int cur = 0;
    for(int i = 0; i < len; i++)
    {
        int p = t[i] - 'a';
        if(!trie[cur][p])
            return 0;
        cur = trie[cur][p];
    }
    return sum[cur];
}
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    memset(trie, 0, sizeof(trie));
    memset(sum, 0, sizeof(sum));
    while(gets(s) != NULL)
    {
        if(s[0] == '\0')
            break;
        inserts(s);
    }
    while(scanf("%s", s) != EOF)
    {
        cout << searchs(s) << endl;
    }
}

代码3:结构体指针形式的字典树

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[10+10];
struct Trie
{
    Trie* next[26];
    int sum;
    Trie()
    {
        for(int i = 0; i < 26; i++)
            next[i] = NULL;
        sum = 0;
    }
}root;
void inserts(char *s)
{
    Trie* p = &root;
    int len = strlen(s);
    for(int i = 0; i < len; i++)
    {
        int cur = s[i] - 'a';
        if(p->next[cur] == NULL)
        {
            p->next[cur] = new Trie;
        }
        p = p->next[cur];
        p->sum++;
    }
}
int finds(char *s)
{
    Trie* p = &root;
    int len = strlen(s);
    for(int i = 0; i < len; i++)
    {
        int cur = s[i] - 'a';
        if(p->next[cur] == NULL)
            return 0;
        else
            p = p->next[cur];
    }
    return p->sum;
}


int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while(gets(s) != NULL)
    {
        if(s[0] == '\0')
            break;
        inserts(s);
    }
    while(scanf("%s", s) != EOF)
    {
        cout << finds(s) << endl;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • Dungeon Master POJ - 2251(bfs)

    _DIY
  • CF: Long Number

    分析1:题目原文中有这么一句“You can perform the following operation no more than once: choose...

    _DIY
  • 算法细节系列(35):不一样的排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • C++primer学习笔记(二)

    1 使用数组初始化vector:int int_arr[arr_size] = {0,1,2,3}; vector<int> ivec(int_arr, int...

    震八方紫面昆仑侠
  • 分治算法

    // 二分查找的思路,halfLen 是中位数的right 所以必须 m + n + 1 // 中位数是可以将数组分割为左右相等的数组,一个数将其分为左右相等...

    用户7625070
  • gcd,哈希问题-LeetCode 357、355、365、367、380

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。

    算法工程师之路
  • 51Nod-1203-JZPLCM

    ACM模版 描述 ? 题解 这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。 首先将数进行拆解,拆...

    f_zyj
  • P1828 香甜的黄油 Sweet Butter

    题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜...

    attack
  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack

扫码关注云+社区

领取腾讯云代金券