庆阳市建设局海绵城市网站,注册规划师报考条件2022,网页ui设计是什么,怎么做网站埋点#xff08;Trie Tree#xff09;字典树
场景#xff1a;在n个字符串中查找某个字符串。
暴力匹配#xff0c;时间复杂度为O#xff08;nm#xff09;#xff0c;m为字符串平均长度#xff0c;效率过低。
字典查找单词fly#xff0c;首先查找’f’,然后…Trie Tree字典树
场景在n个字符串中查找某个字符串。
暴力匹配时间复杂度为Onmm为字符串平均长度效率过低。
字典查找单词fly首先查找’f’,然后查找’l’,最后查找’y’,实现查找字典树就是完成模拟查找过程。
例
bebeemaymanmomhe
通过这6个单词构造字典树
在每次单词的节点处设置标记是否为单词结尾。
字典树应用
字符串检索统计单词出现的次数前缀匹配字符串排序
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);//单词前缀MapMapString, 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[][]trienew int[1000010][26];//数组定义字典树存储下一个字符的位置static int[]numnew int[1000010];//以某个字符为前缀的单词数量static int pos1;//当前新分配存储数量/*** 向字典树中插入单词*/public static void insert(char[]str){int p0;for (int i 0; i str.length; i) {int nstr[i]-a;if(trie[p][n]0){trie[p][n]pos;}ptrie[p][n];num[p];}}/**** param str 字符数组* return 以字符串为前缀的单词数量*/public static int find(char[] str){int p0;for (int i 0; i str.length; i) {int nstr[i] - a;if(trie[p][n] 0)return 0;ptrie[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[]chss.toCharArray();insert(chs);}while (in.hasNext()) {String query in.nextLine();char[]chsquery.toCharArray();System.out.println(find(chs));}}}
