hdu 5687 Problem C 字典樹

傳送門：hdu 5687 Problem C

中文題目就不做過多的解釋

解題思路

定義一個結構體，裡面有26個字母，就像下面這樣：

struct Node{
    int next[];
    int sum;
    void init()
    {
        sum = ;
        memset(next,-,sizeof next);
    }
};
           

然後定義一個這個類型root[MAXN]數組，表示到每個單詞的編号，比如root[1].next[0] = x，就表示目前節點連接配接的下一個節點是0通過x到達。

增加函數

就不用過多贅述了，因為幾本書與模闆類型。

查詢函數

建議傳回的是查詢單詞字母一個出現了多少個，因為這樣會友善删除操作

删除函數

就是将這個單詞對應的路上删除對應的數量

AC代碼

#include<cstdio>
#include<cstring>
const int MAXN = ;
int tot = ;
struct Node{
    int next[];
    int sum;
    void init()
    {
        sum = ;
        memset(next,-,sizeof next);
    }
};
Node root[MAXN];
void add(char *str)
{
    int len = strlen(str);
    int start = ;
    for(int i=;i<len;i++)
    {
        int id = str[i] - 'a';
        if(root[start].next[id] == -)
        {
            root[start].next[id]=tot++;
        }
        start = root[start].next[id];
        root[start].sum++;
    }
}
int search(char *str)
{
    int len = strlen(str);
    int start = ;
    for(int i=;i<len;i++)
    {
        int id = str[i] - 'a';
        if(root[start].next[id] == -)
            return ;
        start = root[start].next[id];
    }
    return root[start].sum;
}
void del(char *str,int cnt)
{
    int len = strlen(str);
    int start = ;
    if(cnt<) return ;
    for(int i=;i<len;i++)
    {
        int id = str[i] - 'a';
        if(root[start].next[id] == -)
            return ;
        root[start].sum-=cnt;
        start = root[start].next[id];
    }
    root[start].sum = ;
    for(int i=;i<;i++)
        root[start].next[i] = -;
}

int main()
{
    int T;
    char str[],word[];
    scanf("%d",&T);
    for(int i=;i<MAXN;i++)
        root[i].init();
    while(T--)
    {
        scanf("%s%s",str,word);
        if(str[] == 'i')
            add(word);
        else if(str[] == 's')
            if(search(word)>) printf("Yes\n");
            else printf("No\n");
        else
            del(word,search(word));
    }
    return ;
}
           

我同學用動态申請記憶體的方法AC代碼

#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define FIN freopen("in.txt", "r", stdin);
#define FOUT freopen("out.txt", "w", stdout);
#define lson l, mid, cur << 1
#define rson mid + 1, r, cur << 1 | 1
const int INF = ;
const LL INFLL = LL;
const int MAXN =  + ;
const int MAXM =  + ;
const int MOD =  + ;

struct node
{
    int v;
    node* nxt[];
    node()
    {
        v = ;
        memset(nxt, NULL, sizeof(nxt));
    }
};

void trie_insert(node* root, char* word)
{
    node* now = root;
    int len = strlen(word);
    for (int i = ; i < len; i++)
    {
        int id = word[i] - 'a';
        if (now->nxt[id] == NULL)
            now->nxt[id] = new node();
        now = now->nxt[id];
        now->v++;
    }
}

void trie_delete(node* root, char* word)
{
    node* now = root;
    int len = strlen(word), del;
    for (int i = ; i < len; i++)
    {
        int id = word[i] - 'a';
        if (now->nxt[id] == NULL)
            return;
        now = now->nxt[id];
        del = now->v;
    }
    now = root;
    for (int i = ; i < len; i++)
    {
        int id = word[i] - 'a';
        if (now->nxt[id] == NULL)
            return;
        if (i == len - )
        {
            free(now->nxt[id]);
            now->nxt[id] = NULL;
            return;
        }
        now = now->nxt[id];
        now->v -= del;
    }
}

bool trie_query(node* root, char* word)
{
    node* now = root;
    int len = strlen(word);
    int ans = INF;
    for (int i = ; i < len; i++)
    {
        int id = word[i] - 'a';
        if (now->nxt[id] == NULL)
            return false;
        now = now->nxt[id];
    }
    return now->v != ;
}

int main()
{
    int n;
    scanf("%d", &n);
    char op[], word[];
    node* root = new node();
    while (n--)
    {
        scanf("%s%s", op, word);
        if (strcmp(op, "insert") == )
            trie_insert(root, word);
        else if (strcmp(op, "delete") == )
            trie_delete(root, word);
        else
            printf("%s\n", trie_query(root, word) ? "Yes" : "No");
    }
    return ;
}