Trie入门与模板

简介

Trie ，又称前缀树或者是字典树，不仅在字符串的应用广泛，在数据结构中也有很多相应的题目，是数据结构中用空间兑换时间的典型。

下面是两个入门题

HDU 1251 统计难题

题意：
给定多个字符串，多个询问，问你以所询问字符串为前缀的字符串数量。

思路：
构造Trie，插入的时候打个顺便再对前缀计数即可。

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000005;
int ch[N][30], val[N], sz;

void insert(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k]) {
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 1;
            ch[u][k] = sz++;
        }
        else
            val[ch[u][k]]++;
        u = ch[u][k];
    }
}

int query(char *s) 
{
    int u = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int k = s[i] - 'a';
        if (!ch[u][k])
            return 0;
        u = ch[u][k];
    }
    return val[u];
}

int main() 
{
    char str[15];
    memset(ch[0], 0, sizeof(ch[0]));
    sz = 1;
    while (gets(str) && strlen(str) != 0)
        insert(str);
    while (scanf("%s", str) == 1)
        printf("%d\n", query(str));
    return 0;
}

HDU 1075 What Are You Talking About

题意：
给定字符串以及映射的字符串，再给定另几个字符串，让你把映射后的写出来。

思路：
大致的思路都是有的，构建Trie，再对每个单词进行查询。
但是！！！有非常非常多的坑！！！我觉得字符串的坑都这么多！！！
但是我写这篇博文实际上是我A题一周后了，具体哪些我也忘了……想知道，就看代码或者discuss吧。
真的是坑哭了…… 交了22发才A……

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 500010;
const int sigma_size = 27;

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};

int main()
{
    Trie trie;
    char str[2][15];
    char buf[3005], ch;
    int id=0;
    scanf("%s", str[0]);
    while (scanf("%s", str[0]) && strcmp(str[0], "END") != 0) {
        scanf("%s", str[1]);
        trie.insert(str[1], str[0]);
    }
    scanf("%s", str[0]);
    getchar();
    while (scanf("%c", &ch)) {
        if (isalpha(ch))
            buf[id++] = ch;
        else {
            buf[id] = '\0';
            id = 0;
            if (strcmp(buf, "END") == 0)
                break;
            trie.query(buf);
            putchar(ch);
        }
    }
    return 0;
}

指针模板

query函数针对的是 hdu 1075

struct TrieNode {
    TrieNode* nxt[sigma_size];
    char* trans;
    char ch;
    bool isEnd;
    TrieNode()
    {
        trans = NULL;
        isEnd = false;
        memset(nxt, 0, sizeof ch);
    }
    ~TrieNode()
    {
        delete trans;
    }
};

struct Trie {
    TrieNode* root;
    Trie()
    {
        root = new TrieNode;
    }
    ~Trie()
    {
        freeTree(root);
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int len = strlen(s), idx;
        TrieNode *cur = root, *tmp;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                tmp = new TrieNode;
                tmp->ch = s[i];
                cur->nxt[idx] = tmp;
            }
            cur = cur->nxt[idx];
        }
        cur->isEnd=true;
        cur->trans = new char[strlen(tar) + 2];
        memcpy((cur->trans), tar, strlen(tar) + 1);
    }

    void query(char* s)
    {
        int len = strlen(s), idx;
        TrieNode* cur = root;
        for (int i = 0; i < len; i++) {
            idx = getIdx(s[i]);
            if (cur->nxt[idx] == NULL) {
                printf("%s", s);
                return;
            }
            cur = cur->nxt[idx];
        }
        if (cur->isEnd)
            printf("%s", cur->trans);
        else
            printf("%s", s);
    }

    void freeTree(TrieNode* cur)
    {
        for (int i = 0; i < sigma_size; i++)
            if (cur->nxt[i])
                freeTree(cur->nxt[i]);
        delete cur;
    }
};

数组模板

query函数针对的是 hdu 1075

struct Trie {
    int ch[maxn][sigma_size];
    char trans[maxn][12];
    bool isEnd[maxn];
    int sz;
    Trie()
    {
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        isEnd[0] = false;
    }
    int getIdx(const char& c) { return c - 'a'; }

    void insert(char* s, char* tar)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                isEnd[sz] = false;
                ch[u][idx] = sz++;
            }
            u = ch[u][idx];
        }
        memcpy(trans[u], tar, sizeof trans[u]);
        isEnd[u] = true;
    }

    void query(char* s)
    {
        int u = 0, len = strlen(s);
        for (int i = 0; i < len; i++) {
            int idx = getIdx(s[i]);
            if (!ch[u][idx]) {
                printf("%s", s);
                return;
            }
            u = ch[u][idx];
        }
        if (isEnd[u])
            printf("%s", trans[u]);
        else
            printf("%s", s);
    }
};