HDU 1251 统计难题 codevs 4189 字典

字典树

字典树，Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串)。

所以经常被搜索引擎系统用于文本词频统计

学习：https://www.cnblogs.com/TheRoadToTheGold/p/6290732.html

HDU 1251（前缀出现次数）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

char s[12];
int tot, trie[400005][26], sum[400005];

void plug(char * s)
{
    int root = 0;
    for(int i = 0; s[i]; ++i)
    {
        int x = s[i] - 'a';
        if(trie[root][x] == 0)
            trie[root][x] = ++tot;
        sum[ trie[root][x] ]++;  ///记下该前缀出现次数
        root = trie[root][x];
    }
}

int found(char * s)
{
    int root = 0;
    for(int i = 0; s[i]; ++i)
    {
        int x = s[i] - 'a';
        if(trie[root][x] == 0)
            return 0;
        root = trie[root][x];
    }
    return sum[root];
}

int main()
{
    while(gets(s))///保证接受'空行'这一输入
    {
        if(strlen(s) == 0)
            break;
        else
            plug(s);
    }
    while(cin >> s)
        cout << found(s) << '\n';
    return 0;
}

Codevs 4189（前缀（或整个单词）查找）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2000005;

char s[50];
int tot, n;
int trie[N][26];
///bool is[N]; 查询整个单词时用到


///s[]作为全局变量，这里可以省略形参
void plug(char * s)
{
    int root = 0;
    for(int i = 0; s[i]; ++i)
    {
        int x = s[i] - 'a';
        if(trie[root][x] == 0)
            trie[root][x] = ++tot;
        root = trie[root][x];
    }
    ///is[root] = 1;
}

bool found(char * s)
{
    int root = 0;
    for(int i = 0; s[i]; ++i)
    {
        int x = s[i] - 'a';
        if(trie[root][x] == 0)
            return 0;
        root = trie[root][x];
    }
    return 1;
    ///查询整个单词时，return is[root];
}

int main()
{
    tot = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        cin >> s;
        plug(s);
    }
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        cin >> s;
        if(found(s))
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    return 0;
}