预备知识：左程云初级班p9

    image.png
    功能：

    • 找字符串的公共前缀，可以用来做检索
    • ac自动机中应用了kmp和前缀树的思想。
    • 可以利用前缀树思想做一些贪心策略，这个印象中有一道难题。

    具体建树过程：

    • 用语料构建一颗多叉树（字符就26，更多的话用treeMap来做），比如上图例子中的arr1

    image.png
    一道例题：
    找几个字符串的公共前缀，从这道题给的四种题解看出复杂度还是MN级别的。
    所以不妨用前缀树来实现这道题。
    image.png
    对比我写的和 左程云版本，思考在工程上如何封装组件

    • 这里我的变量全用了public，没有提供set方法，不安全。

    • Tie树初始化的时候用了一个没有实际意义，或者说代表空串的root节点来创建。

      1. public static void main(String[] args) {
      2.       String[] strs = {"flower","flow","flight"};
      3.       String[] strs2 = {"dog","racecar","car"};
      4.       System.out.println(longestCommonPrefix(strs));
      5.       System.out.println(longestCommonPrefix(strs2));
      6.   }
      7.   public static String longestCommonPrefix(String[] strs) {
      8.       Node node = new Node(0,0);
      9.       Trie trie = new Trie(node);
      10.       for(String str : strs){
      11.           char[] chs = str.toCharArray();
      12.           trie.add(chs);
      13.       }
      14.       String str0 = strs[0];
      15.       char[] chs0 = str0.toCharArray();
      16.       int index=0;
      17.       Node cur = node;
      18.       StringBuilder sb = new StringBuilder();
      19.       while(index< chs0.length){
      20.           if(cur.nodes[chs0[index]-'a'] == null) return "";
      21.           if(cur.nodes[chs0[index]-'a'].p == strs.length){
      22.               sb.append(chs0[index]);
      23.               cur = cur.nodes[chs0[index]-'a'];
      24.               index++;
      25.           }
      26.           else {
      27.               break;
      28.           }
      29.       }
      30.       return sb.toString();
      31.   }
      32.   public static class Node{
      33.       int p;
      34.       int e;
      35.       Node[] nodes;
      37.       public Node(int p, int e) {
      38.           this.p = p;
      39.           this.e = e;
      40.           this.nodes = new Node[26];
      41.       }
      42.   }
      44.   public static class Trie{
      45.       Node root;
      47.       public Trie(Node root) {
      48.           this.root = root;
      49.       }
      51.       public void add(char[] chs){
      52.            Node cur = root;
      53.            int index = 0;
      54.            while(index < chs.length){
      55.                if(cur.nodes[chs[index]-'a'] == null ){
      56.                    if(index == chs.length-1){
      57.                        cur.nodes[chs[index]-'a'] = new Node(1,1);
      58.                    }
      59.                    else {
      60.                        cur.nodes[chs[index]-'a'] = new Node(1,0);
      61.                    }
      62.                }else {
      63.                    cur.nodes[chs[index]-'a'].p++;
      64.                    if(index == chs.length-1){
      65.                        cur.nodes[chs[index]-'a'].e++;
      66.                    }
      68.                }
      69.                cur = cur.nodes[chs[index]-'a'];
      70.                index++;
      71.            }
      72.       }
      73.   }

      与左程云版本对比
      考虑的细节：

    • 命名边，用的nexts数组语义好一些

    image.png

    • 当新字符串引入的时候，为root节点p赋值，可以表示当前前缀树维护的语料数量。同时，支持语料中出现“空串”

    image.png

    • 根节点是私有变量，这样的话，如果判断str2是不是str1的前缀，需要Trie类提供方法。而不是自己在调用端书写
    • Node类中变量对Trie是完全开放的，这个跟我写法一致
    • 最后末端end++ 的判断直接放到for循环外，因为i到达chs.length的时候当前节点指的就是末端节点。

    image.png

    其他：
    1、工程上，当字符种类特别多的时候，比如java，字符总共有6万多。
    用哈希，有序哈希等。
    image.png
    2、查询、准确查询，模糊查询
    image.png
    image.png
    3、删除、如果c++需要考虑析构。

    • 删除之前先查询，注意是准确查询语料中是否存在，感觉能用在检索时候的模糊搜索的地方，从语料中过滤掉不合法、不健康的的字符

    image.png
    image.png
    image.png