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

## 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 条评论

• ### CF: Long Number

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

• ### 算法细节系列（35）：不一样的排序

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

• ### C++primer学习笔记（二）

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

• ### 分治算法

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

• ### gcd，哈希问题-LeetCode 357、355、365、367、380

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

• ### 51Nod-1203-JZPLCM

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

• ### P1828 香甜的黄油 Sweet Butter

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

• ### 1751:分解因数

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