字典树小结

使用二维数组保存字典树，用于处理最长字符串等问题
字典树保存用了两类ID，一类是第一位的，依据插入的先后顺序计数
第二类ID是，每个节点上最多有26个子节点，因为英文字母只有26种，所以用插入字符的-‘a’作为第二类值

字典树类模板

class Trie{
    private int fid=0;
    private int tid;
    private int ans = 0;
    private int trie[][] = new int[100][30];
    private final static int MAX = 26;
    void insert(String str){
        char[] array = str.toCharArray();
        int root = 0;
        for(int i=0;i<array.length;i++){
            //获取第二类ID
            tid = array[i]-'a';
            if(trie[root][tid]==0){
                trie[root][tid]=++fid;
            }
            root=trie[root][tid];
        }
    }
    int match(String str){
        char[] array = str.toCharArray();
        int root = 0;
        int count = 0;
        for(int i=0;i<array.length;i++){
            tid = array[i]-'a';
            if(trie[root][tid]==0)
                return count;
            root = trie[root][tid];
        }
        ans = 0;
        getnum(root);
        count = ans; 
        return count;
    }
    void getnum(int root){
        boolean flag = false;
        for(int i=0;i<MAX;i++){
            if(trie[root][i]!=0){
                flag = true;
                getnum(trie[root][i]);
            }
        }
        if(!flag){
            ans++;
            return;
        } 
    }


}