纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

字典树（Trie）

Trie树又被称为前缀树、字典树。只是简单的记录了一下基本的，后面那些不会的应用只能先写着标题，具体代码等后面有机会再学吧。。。

import java.io.*;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    final static int maxn = (int) 1e7 + 6;
    public static int[][] son = new int[maxn][26]; //存储树中每个节点的子节点
    public static int idx = 0; //0号点既是根节点，又是空节点
    public static int[] cnt = new int[maxn]; //存储以每个节点结尾的单词数量

    public static void main(String[] args) throws Exception {

        int n = nextInt();
        while (n-- != 0) {
            String s = nextString();
            char[] sb = s.toCharArray();
            insert(sb);
        }
        int m = nextInt();
        while (m-- != 0) {
            String s = nextString();
            char[] sb = s.toCharArray();
            System.out.println(query(sb));
        }


        closeAll();
    }
    //============================================================
    // 插入一个字符串
    public static void insert(char[] str) {
        int p = 0;
        for (int i = 0; i < str.length; ++i) {
            int v = str[i] - 'a';
            if (son[p][v] == 0) son[p][v] = ++idx;
            p = son[p][v];
        }
        cnt[p]++;
    }

    // 查询字符串出现的次数
    public static int query(char[] str) {
        int p = 0;
        for (int i = 0; i < str.length; ++i) {
            int v = str[i] - 'a';
            if (son[p][v] == 0) return 0;
            p = son[p][v];
        }
        return cnt[p];
    }
    //============================================================

    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }

    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }

    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }

    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }

    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

其他需求操作

字符串出现次数

见上代码。

最长公共前缀（LCP）

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先（LCA）问题。

求以串pre为前缀的单词数量

打印指定前缀的单词

串排序

字符串按字典序排序的结果。

实际应用场景

1. 使用搜索引擎的时候，自动匹配前缀显示后缀。