字典树的实现

package class044;

// 用固定数组实现前缀树，空间使用是静态的。推荐！
// 测试链接 : https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;

public class Code02_TrieTree {

	// 如果将来增加了数据量，就改大这个值
	public static int MAXN = 150001;

	public static int[][] tree = new int[MAXN][26];

	public static int[] end = new int[MAXN];

	public static int[] pass = new int[MAXN];

	public static int cnt;

	public static void build() {
		cnt = 1;
	}

	public static void insert(String word) {
		int cur = 1;
		pass[cur]++;
		for (int i = 0, path; i < word.length(); i++) {
			path = word.charAt(i) - 'a';
			if (tree[cur][path] == 0) {
				tree[cur][path] = ++cnt;
			}
			cur = tree[cur][path];
			pass[cur]++;
		}
		end[cur]++;
	}

	public static int search(String word) {
		int cur = 1;
		for (int i = 0, path; i < word.length(); i++) {
			path = word.charAt(i) - 'a';
			if (tree[cur][path] == 0) {
				return 0;
			}
			cur = tree[cur][path];
		}
		return end[cur];
	}

	public static int prefixNumber(String pre) {
		int cur = 1;
		for (int i = 0, path; i < pre.length(); i++) {
			path = pre.charAt(i) - 'a';
			if (tree[cur][path] == 0) {
				return 0;
			}
			cur = tree[cur][path];
		}
		return pass[cur];
	}

	public static void delete(String word) {
		if (search(word) > 0) {
			int cur = 1;
			for (int i = 0, path; i < word.length(); i++) {
				path = word.charAt(i) - 'a';
				if (--pass[tree[cur][path]] == 0) {
					tree[cur][path] = 0;
					return;
				}
				cur = tree[cur][path];
			}
			end[cur]--;
		}
	}

	public static void clear() {
		for (int i = 1; i <= cnt; i++) {
			Arrays.fill(tree[i], 0);
			end[i] = 0;
			pass[i] = 0;
		}
	}

	public static int m, op;

	public static String[] splits;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		String line = null;
		while ((line = in.readLine()) != null) {
			build();
			m = Integer.valueOf(line);
			for (int i = 1; i <= m; i++) {
				splits = in.readLine().split(" ");
				op = Integer.valueOf(splits[0]);
				if (op == 1) {
					insert(splits[1]);
				} else if (op == 2) {
					delete(splits[1]);
				} else if (op == 3) {
					out.println(search(splits[1]) > 0 ? "YES" : "NO");
				} else if (op == 4) {
					out.println(prefixNumber(splits[1]));
				}
			}
			clear();
		}
		out.flush();
		in.close();
		out.close();
	}

}

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>

typedef struct tn {
    int pass;
    int end;
    struct tn **children;  // 存放子节点的指针
} node;

node *new_node() {
    node *new_node = malloc(sizeof(node));
    new_node->pass = 0;
    new_node->end = 0;
    new_node->children = (node **) calloc(26, sizeof(node *));
    return new_node;
}

void destroy_node(node *node) {
    free(node->children);
    free(node);
}

void destroy_whole_path(node *node) {
    for (int i = 0; i < 26; i++) {
        if (node->children[i] != NULL) {
            destroy_node(node->children[i]);
        }
    }
    destroy_node(node);
}

typedef node *trie;

trie new_trie() {
    return new_node();
}

void insert(trie trie, char *word) {
    if (word == NULL || strlen(word) == 0) {
        return;
    }
    int len = (int) strlen(word);
    node *cur = trie;
    cur->pass++;
    int path;
    for (int i = 0; i < len; i++) {
        path = word[i] - 'a';
        if (cur->children[path] == NULL) {
            cur->children[path] = new_node();
        }
        cur = cur->children[path];
        cur->pass++;
    }
    cur->end++;
}

bool search(trie trie, char *word) {
    if (word == NULL || strlen(word) == 0) {
        return false;
    }
    node *cur = trie;
    int path;
    for (int i = 0; i < strlen(word); i++) {
        path = word[i] - 'a';
        if (cur->children[path] == NULL) {
            return false;
        }
        cur = cur->children[path];
    }
    return cur->end != 0;
}

void delete(trie trie, char *word) {
    if (!search(trie, word)) {
        return;
    }
    node *cur = trie, *next;
    cur->pass--;
    int path;
    for (int i = 0; i < strlen(word); i++) {
        path = word[i] - 'a';
        if (--cur->children[path]->pass == 0) {
            next = cur->children[path];
            cur->children[path] = NULL;
            destroy_whole_path(next);
            return;
        }
        cur = cur->children[path];
    }
    cur->end--;
}

int prefixNumber(trie trie, char *word) {
    if (word == NULL || strlen(word) == 0) {
        return false;
    }
    node *cur = trie;
    int path;
    for (int i = 0; i < strlen(word); i++) {
        path = word[i] - 'a';
        if (cur->children[path] == NULL) {
            return 0;
        }
        cur = cur->children[path];
    }
    return cur->pass;
}

#define MAXLEN 21

int main(void) {
    trie trie = new_trie();
    int n, op;
    char str[MAXLEN];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%s", &op, str);
        if (op == 1) insert(trie, str);
        else if (op == 2) delete(trie, str);
        else if (op == 3) printf("%s\n", search(trie, str) ? "YES" : "NO");
        else if (op == 4) printf("%d\n", prefixNumber(trie, str));
    }
    destroy_node(trie);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;  // 结点总出现数

int cnt; // 当前结点(第几个结点)
int Tree[N][26]; // 结点路径记录表
int pass[N]; // 该结点的通过数
int endd[N]; // 该结点作为末尾数

// 单词插入:
void word_insert(string word)
{
    int tool=1; // 遍历工具 - 从第 1 个结点开始
    int path=0; // 路径记录

    pass[tool]++; // 第一个结点通过数++

    // 遍历单词 从第二个结点开始记录
    for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
    {
        path = c - 'a';  // 第 1 & 2 结点之间的路径

        // 没有该结点:
        if(Tree[tool][path]==0)
        {
            // 添加结点:
            Tree[tool][path] = ++cnt;

            // 遍历工具访问下一结点，结点通过数++
            tool = Tree[tool][path];
            pass[tool]++;
        }
        // 有对应结点:
        else
        {
            // 遍历工具访问下一结点，结点通过数++
            tool = Tree[tool][path];
            pass[tool]++;
        }
    }

    // 结点作为末尾数++
    endd[tool]++;
    return;
}   

// 单词查重:
int word_duplicate(string word)
{
    int tool=1; // 遍历工具 - 从第 1 个结点开始
    int path=0; // 路径记录

    // 遍历单词 从第二个结点开始记录
    for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
    {
        path = c - 'a';  // 第 1 & 2 结点之间的路径

        // 没有该结点:
        if(Tree[tool][path]==0)
        {
            return 0;
        }
        // 有对应结点:
        else
        {
            // 遍历工具访问下一结点，结点通过数++
            tool = Tree[tool][path];
        }
    }

    // 返回结点作为末尾数:
    return endd[tool];
}

void word_delete(string word)
{
    // 没有该单词
    if(!word_duplicate(word))
    {
        return;
    }
    // 有该单词:
    else
    {
        int tool=1; // 遍历工具 - 从第 1 个结点开始
        int path=0; // 路径记录

        pass[tool]--; // 第一个结点通过数++

        // 遍历单词 从第二个结点开始记录
        for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
        {
            path = c - 'a';  // 第 1 & 2 结点之间的路径

            pass[Tree[tool][path]]--;

            // 该路径没被复用过，仅仅记录一次:
            if(pass[Tree[tool][path]]==0)
            {
                Tree[tool][path]=0;
                return;
            }
            // 该路径被复用过:
            else
            {
                tool = Tree[tool][path];
            }
        }

        // 结点作为末尾数--
        endd[tool]--;
        return;
    }
}

int word_pre(string word)
{
    int tool=1; // 遍历工具 - 从第 1 个结点开始
    int path=0; // 路径记录

    // 遍历单词 从第二个结点开始记录
    for(const auto& c : word) // 第 1 & 2 结点之间的路径表示单词的第一个字母
    {
        path = c - 'a';  // 第 1 & 2 结点之间的路径

        // 没有该结点:
        if(Tree[tool][path]==0)
        {
            return 0;
        }
        // 有对应结点:
        else
        {
            // 遍历工具访问下一结点
            tool = Tree[tool][path];
        }
    }
    // 返回结点通过数:
    return pass[tool];
}

void clear()
{
    memset(&Tree[0][0] , 0 , sizeof(int)*26*(cnt+1));
    memset(&pass[0] , 0 , sizeof(int)*(cnt+1));
    memset(&endd[0] , 0 , sizeof(int)*(cnt+1));
    cnt=1;
}

int main()
{
    cnt=1;

    int n;
    cin >> n;

    while(n--)
    {
        int x;
        string word;

        cin >> x >> word;

        if(x==1)
        {
            word_insert(word);
        }
        else if(x==2)
        {
            word_delete(word);
        }
        else if(x==3)
        {
            cout << (word_duplicate(word)>0 ? "YES" : "NO") << endl;
        }
        else
        {
            cout << word_pre(word) << endl;
        }
    }

    clear();

    return 0;
}

// 已经AC的代码
#include<iostream>
#include<string>
using namespace std;

void insert(string word);
void delete_(string word);		// delete 是关键字，这里改为 delete_ 
bool search(string word);
int prefixNumber(string pre);

class TrieNode {	// 在后续函数中全部改为指针形式 
   public:
      int path = 0;
      int end = 0;
	  TrieNode *map[26] = {NULL};	// 注意这里要加 * 号 ，注意一定要把指向对象的数组指向NULL 
};

TrieNode *root = new TrieNode();	// 注意一定要写 new TrieNode() 

void insert(string word) {
	if (word.empty()) {
		return;
	}
	TrieNode *node = root;
	node->path++;
	int index = 0;
	for (int i = 0; i < word.size(); i++) {
		index = word[i] - 'a';
		if (node->map[index] == NULL) {
			node->map[index] = new TrieNode();
		}
		node = node->map[index];
		node->path++;
	}
	node->end++;
}

void delete_(string word) {
	if (search(word)) {
		TrieNode *node = root;
		node->path++;
		int index = 0;
		for (int i = 0; i < word.size(); i++) {
			index = word[i] - 'a';
			if (node->map[index]->path-- == 1) {
				node->map[index] = NULL;
				return;
			}
			node = node->map[index];
		}
		node->end--;
	}
}

bool search(string word) {
	if (word.empty()) {
		return false;
	}
	TrieNode *node = root;
	int index = 0;
	for (int i = 0; i < word.size(); i++) {
		index = word[i] - 'a';
		if (node->map[index] == NULL) {
			return false;
		}
		node = node->map[index];
	}
	return node->end != 0;
}

int prefixNumber(string pre) {
	if (pre.empty()) {
		return 0;
	}
	TrieNode *node = root;
	int index = 0;
	for (int i = 0; i < pre.size(); i++) {
		index = pre[i] - 'a';
		if (node->map[index] == NULL) {
			return 0;
		}
		node = node->map[index];
	}
	return node->path;
}

int main() {
	int m;
	cin >> m;
	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			string word;
			cin >> word;
			insert(word);
		}
		if (op == 2) {
			string word;
			cin >> word;
			delete_(word);
		}
		if (op == 3) {
			string word;
			cin >> word;
			bool res = search(word);
			cout << (res ? "YES" : "NO") << endl;
		}
		if (op == 4) {
			string word;
			cin >> word;
			int res = prefixNumber(word);
			cout << res << endl;
		}
	}
	return 0;
}

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

const int N = 26;
class Node{
	public:
		Node();
		~Node();
		/*
		void insert(string word);
		void deleteStr(string word);
		bool search(string word);
		int prefixNumber(string pre);
		*/
		int pass;
		int end;
		Node *next[N];
};
Node::Node()
{
	this->pass = 0;
	this->end = 0;
	memset(this->next,NULL,sizeof(next));
}
Node::~Node()
{
	for(int i = 0; i < N; i++)
	{
		if(this->next[i] != NULL)
		{
			delete this->next[i];
			this->next[i] = NULL;
		}
	}
}
bool search(Node * root ,string word);
//op = 1
void insert(Node * root , string word)
{
	if(word.size() == 0)
		return;
	Node* node = root;
	node->pass++;
	int index = 0;
	for(int i = 0; i < word.size() ; i++)
	{
		index = word[i] - 'a';
		if(node->next[index] == NULL)
			node->next[index] = new Node;
		node = node->next[index];
		node->pass++;
	}
	node->end++;
} 
//op = 2
void deleteStr(Node *root ,string word)
{
	if(!search(root,word))
		return;
	Node *node = root;
	int index = 0;
	node->pass--;
	for(int i = 0; i < word.size(); i++)
	{
		index = word[i] - 'a';
		node->next[index]->pass--;
		if(node->next[index]->pass == 0)
		{
			delete node->next[index];
			node->next[index] = NULL;
			return;
		}
		node = node->next[index];	
	}
}
//op = 3
bool search(Node * root ,string word)
{
	if(word.size() == 0)
		return false;
	Node *node = root;
	int index = 0;
	for(int i = 0 ; i < word.size() ; i++)
	{
		index = word[i] - 'a';
		if(node->next[index] == NULL)
			return false;
		node = node->next[index];
	}
	return true;
}
//op = 4
int prefixNumber(Node * root ,string pre)
{
	if(pre.size() == 0)
		return root->pass;
	Node *node = root;
	int index = 0;
	for(int i = 0; i < pre.size(); i++)
	{
		index = pre[i] - 'a';
		node = node->next[index];
	} 
	return node->pass;
}
int main(){
	Node *root = new Node;
	int m ;
	cin >> m;

	for(int i = 0; i < m; i++)
	{
		int op;
		string str;
		cin >> op;
		cin >> str;
		if(op == 1)
			insert(root,str);
		else if(op == 2)
			deleteStr(root,str);
		else if(op == 3)
			cout << (search(root,str) ? "YES" : "NO") << endl;
		else if(op == 4) 
			cout << prefixNumber(root,str) << endl;
	}
	delete root;
	return 0;	
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
    // 根节点
    private static TireNode root = new TireNode();
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int opNum = in.nextInt();
        while (opNum-- > 0) {
            int op = in.nextInt();
            String str = in.next();
            switch (op) {
                case 1:
                    addNode(str);
                    break;
                case 2:
                    delNode(str);
                    break;
                case 3:
                    System.out.println(ifExitNode(str) ? "YES" : "NO");
                    break;
                case 4:
                    System.out.println(getSubNodeCnt(str));
            }
        }
    }
 
    private static int getSubNodeCnt(String prefix) {
        TireNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.subNode.containsKey(c)) {
                return 0;
            }
            node = node.subNode.get(c);
        }
        return node.cnt;
    }
 
    private static boolean ifExitNode(String str) {
        TireNode node = root;
        for (char c : str.toCharArray()) {
            if (!node.subNode.containsKey(c)) {
                return false;
            }
            node = node.subNode.get(c);
        }
        return node.end != 0;
    }
 
    // 删除node的时候 每次只能删一个 即使重复了好几个 每次也只能删一个
    private static void delNode(String str) {
        TireNode node = root;
        for (char c : str.toCharArray()) {
            node = node.subNode.get(c);
            node.cnt--;
        }
        node.end--;
        if (node.cnt == 0) {
            node.subNode = new HashMap<>();
        }
    }
 
    // 可以重复添加的node
    private static void addNode(String str) {
        TireNode node = root;
        for (char c : str.toCharArray()) {
            if (!node.subNode.containsKey(c)) {
                node.subNode.put(c, new TireNode());
            }
            node = node.subNode.get(c);
            node.cnt++;
        }
        node.end++;
    }
 
    static class TireNode {
        // 其实可以换成数组
        public Map<Character, TireNode> subNode = new HashMap<>();
        // 多少个单词路过这个节点
        public int cnt = 0;
        // 这个节点是多少个单词的结尾
        // 这点可以重复添加，这是最骚的
        public int end = 0;
    }
}