（Trie Tree）字典树

场景：在n个字符串中查找某个字符串。

暴力匹配，时间复杂度为O（nm），m为字符串平均长度，效率过低。

字典查找单词"fly"，首先查找’f’,然后查找’l’,最后查找’y’,实现查找，字典树就是完成模拟查找过程。

例：

1. be
2. bee
3. may
4. man
5. mom
6. he

通过这6个单词构造字典树：

在每次单词的节点处设置标记，是否为单词结尾。

字典树应用：

1. 字符串检索
2. 统计单词出现的次数
3. 前缀匹配
4. 字符串排序

HDU1251
问题链接

问题：

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

输入：

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

输出：

对于每个提问,给出以该字符串为前缀的单词的数量.

输入样例：

banana
band
bee
absolute
acmba
b
band
abc

输出样例：

2
3
1
0

使用Map：

import java.util.*;class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);//单词前缀MapMap<String, Integer> prefix = new HashMap<>();while (true) {String s = in.nextLine();if (s.equals("")) {break;}//空行单词表结束for (int i = s.length(); i > 0; i--) {//向map里添加数据String tmp = s.substring(0, i);prefix.put(tmp, prefix.getOrDefault(tmp, 0) + 1);}}while (in.hasNext()) {String query = in.nextLine();System.out.println(prefix.getOrDefault(query, 0));}}}

使用数组构造字典树结构体：

import java.util.*;class Main {static int[][]trie=new int[1000010][26];//数组定义字典树，存储下一个字符的位置static int[]num=new int[1000010];//以某个字符为前缀的单词数量static int pos=1;//当前新分配存储数量/*** 向字典树中插入单词*/public static void insert(char[]str){int p=0;for (int i = 0; i < str.length; i++) {int n=str[i]-'a';if(trie[p][n]==0){trie[p][n]=pos++;}p=trie[p][n];num[p]++;}}/**** @param   str 字符数组* @return  以字符串为前缀的单词数量*/public static int find(char[] str){int p=0;for (int i = 0; i < str.length; i++) {int n=str[i] - 'a';if(trie[p][n] == 0)return 0;p=trie[p][n];}return num[p];}public static void main(String[] args) {Scanner in = new Scanner(System.in);while (true) {String s = in.nextLine();if (s.equals("")) {break;}//空行单词表结束char[]chs=s.toCharArray();insert(chs);}while (in.hasNext()) {String query = in.nextLine();char[]chs=query.toCharArray();System.out.println(find(chs));}}}