Trie树模板

佚名 4年前 (2020-01-26) 算法 2085人围观抢沙发百度已收录

用于快速的查找一个字符串

　　　　  static final int max=100005;　　　　 //所有字符总数
        static int son[][]=new int[max][26];//son数组存储每个节点的儿子；一维表示父节点下标，二维表示小写字母 son[x][0~25]
        static int cnt[]=new int[max];      //cnt[i]存储以下标i为结点的字符串的数量；
        static int idx;                     //idx表示当前用到了那个下标,下标是0的点既是根节点又是空节点
        static void insert(String s){
                int p=0;
                for(int i=0;i<s.length();i++){
                        int u=s.charAt(i)-'a';
                        if(son[p][u]==0) son[p][u]=++idx;
                        p=son[p][u];
                }
                cnt[p]++;
        }
        static int query(String s){
                int p=0;
                for(int i=0;i<s.length();i++){
                        int u=s.charAt(i)-'a';
                        if(son[p][u]==0) return 0;
                        p=son[p][u];
                }
                return cnt[p];
        }