14前缀树 _前缀

少年击剑更吹箫，剑气箫心一例消。这篇文章主要讲述14前缀树相关的知识，希望能为你提供帮助。
前缀树的性质

1、单个字符串中，字符串从前到后的加到一颗多叉树上 2、字符放在路上，节点上有专属的数据项(常见的是pass和end值) 3、所有样本都这样添加，如果没有路就新建，如有路就复用 4、沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1。

【14前缀树】

文章图片

//所有字符串都是a~z小写 public static class Node1 private int pass; private int end; private Node1[] nexts; publicNode1() pass=0; end=0; //本程序假设数组字符串全都是小写的字母，所以初始化每个节点下面都有26个节点 nexts =new Node1[26]; //方法1 public static class Trie1 private Node1 root; public Trie1() root=new Node1(); //在数组中新增一个字符串 publicvoid insert(String word) if (word == null) return; //将字符串转化成字符 char[] chars = word.toCharArray(); //一个引用(相当于一个箭头)，从头结点出发 Node1 node= root; //新加字符串，头节点的pass值+1 node.pass++; int path=0; //从左到右遍历字符 for (int i = 0; i < chars.length; i++) //由字符决定走哪条路，对应的ASCII相减：a-a=0 b-a=1 path=chars[i] - a; //如果下一个节点为空，证明没有出现过，则新建节点 if(node.nexts[path]==null) node.nexts[path]=new Node1(); //node跳到新建的节点上 node =node.nexts[path]; node.pass++; //一个字符串走到终点时，end+1 node.end++; //查询word这个单词之前加入过几次 publicint search(String word) if(word==null) return 0; char[] chars = word.toCharArray(); //将箭头初始化为头节点 Node1 node=root; int path=0; for (int i=0; i< chars.length; i++) path = chars[i] -a; if(node.nexts[path]==null) return 0; node=node.nexts[path]; return node.end; //所有加入的字符串中，有几个是以pre这个这个字符串作为前缀的 public int prefixNumber(String word) if (word==null) return 0; char[] chars = word.toCharArray(); Node1 node=root; int path =0; for(int i=0; i< chars.length; i++) path = chars[i] - a; if(node.nexts[path]==null) return 0; node=node.nexts[path]; return node.pass; //删除一个字符串 public void delete(String word) //先去查询一下看是否有word字符串，如果有，再进行删除，没有就直接跳出 if(search(word)!=0) char[] chars = word.toCharArray(); //指针指向头节点 Node1 node=root; //头节点的pass值减1 node.pass--; int path=0; for (int i=0; i< chars.length; i++) path = chars[i] -a; //如果当前节点的下一个节点的pass值为0，则当前节点的下一个节点指向空，之后的节点都没有意义了，没必要走下去 if (--node.nexts[path].pass==0) node.nexts[path]=node; return; node=node.nexts[path]; node.end--;

//方法2：支持多种类字符 public static class Node2 public int pass; public int end; public HashMap< Integer, Node2> nexts; public Node2() pass = 0; end = 0; nexts = new HashMap< > (); public static class Trie2 private Node2 root; public Trie2() root=new Node2(); //加入一个字符串 public void insert(String word) if(word==null) return; char[] chars = word.toCharArray(); Node2 node=root; node.pass++; int path =0; for (int i=0; i< chars.length; i++) path = (int)chars[i]; if (!node.nexts.containsKey(path)) node.nexts.put(path,new Node2()); node=node.nexts.get(path); node.pass++; node.end++; public void delete(String word) if (search(word) != 0) char[] chs = word.toCharArray(); Node2 node = root; node.pass--; int index = 0; for (int i = 0; i < chs.length; i++) index = (int) chs[i]; if (--node.nexts.get(index).pass == 0) node.nexts.remove(index); return; node = node.nexts.get(index); node.end--; // word这个单词之前加入过几次 public int search(String word) if (word == null) return 0; char[] chs = word.toCharArray(); Node2 node = root; int index = 0; for (int i = 0; i < chs.length; i++) index = (int) chs[i]; if (!node.nexts.containsKey(index)) return 0; node = node.nexts.get(index); return node.end; // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的 public int prefixNumber(String pre) if (pre == null) return 0; char[] chs = pre.toCharArray(); Node2 node = root; int index = 0; for (int i = 0; i < chs.length; i++) index = (int) chs[i]; if (!node.nexts.containsKey(index)) return 0; node = node.nexts.get(index); return node.pass;

//对数器 public static class Right private HashMap< String, Integer> box; public Right() box = new HashMap< > (); public void insert(String word) if (!box.containsKey(word)) box.put(word, 1); else box.put(word, box.get(word) + 1); public void delete(String word) if (box.containsKey(word)) if (box.get(word) == 1) box.remove(word); else box.put(word, box.get(word) - 1); public int search(String word) if (!box.containsKey(word)) return 0; else return box.get(word); public int prefixNumber(String pre) int count = 0; for (String cur : box.keySet()) if (cur.startsWith(pre)) count += box.get(cur); return count; // for test public static String generateRandomString(int strLen) char[] ans = new char[(int) (Math.random() * strLen) + 1]; for (int i = 0; i < ans.length; i++) int value = https://www.songbingjia.com/android/(int) (Math.random() * 6); ans[i] = (char) (97 + value); return String.valueOf(ans); // for test public static String[] generateRandomStringArray(int arrLen, int strLen) String[] ans = new String[(int) (Math.random() * arrLen) + 1]; for (int i = 0; i < ans.length; i++) ans[i] = generateRandomString(strLen); return ans; public static void main(String[] args) int arrLen = 100; int strLen = 20; int testTimes = 100000; for (int i = 0; i < testTimes; i++) String[] arr = generateRandomStringArray(arrLen, strLen); Trie1 trie1 = new Trie1(); Trie2 trie2 = new Trie2(); Right right = new Right(); for (int j = 0; j < arr.length; j++) double decide = Math.random(); if (decide < 0.25) trie1.insert(arr[j]); trie2.insert(arr[j]); right.insert(arr[j]); else if (decide < 0.5) trie1.delete(arr[j]); trie2.delete(arr[j]); right.delete(arr[j]); else if (decide < 0.75) int ans1 = trie1.search(arr[j]); int ans2 = trie2.search(arr[j]); int ans3 = right.search(arr[j]); if (ans1 != ans2 || ans2 != ans3) System.out.println("Oops!"); else int ans1 = trie1.prefixNumber(arr[j]); int ans2 = trie2.prefixNumber(arr[j]); int ans3 = right.prefixNumber(arr[j]); if (ans1 != ans2 || ans2 != ans3) System.out.println("Oops!"); System.out.println("finish!");