[数据结构与算法]前缀树以及相关题目

一个字符串类型的数组arr1，另一个字符串类型的数组arr2。arr2中哪些字符，是arr1中出现的？请打印。arr2中哪些字符，是作为arr1中某个字符串前缀出现的？请打印。arr2中哪些字符，是作为arr1中某个字符串前缀出现的？请打印arr2中出现次数最大的前缀。

前缀树结构。

Java代码：

package com.company;

import java.util.TreeMap;

//前缀树
public class TrieTree {
    public static class TrieNode{
        public int pass;
        public int end;
        public TrieNode[] nexts;

        public TrieNode() {
            pass = 0;
            end = 0;
            nexts = new TrieNode[26];
        }
    }
    public static  class Trie{
        private TrieNode root;
        public  Trie(){
            root = new TrieNode();
        }
        public void insert(String word){
            if (word == null){
                return;
            }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            node.pass++;
            int index = 0;
            for (int i =0; i<chs.length; i++){
                index = chs[i] - 'a';//a就是0，b就是1
                if (node.nexts[index] == null){//有走向a的路吗，没有就新建一条a的路
                    node.nexts[index] = new TrieNode();
                }
                node = node.nexts[index];//然后当前节点移动到下一个节点上（有就直接移动，没有就新建了再移动）
                node.pass++;//然后这个节点的pass++
            }
            node.end++;
        }
        //word这个单词之前加入过几次
        public int search(String word){
            if (word == null){
                return 0;
            }
            char[] chars = word.toCharArray();
            TrieNode node = root;
            int index=0;
            for (int i = 0 ;i<chars.length;i++){
                index = chars[i] - 'a';
                if (node.nexts[index] == null){//如果这个节点后面没有路了，但是循环还没有终止，说明根本没有这个单词。
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }
        //所有加入的字符串中，有几个是以pre这个字符作为前缀的。
        public int prefixNumber(String pre){
            if (pre == null){
                return 0;
            }
            char[] chars = pre.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i =0;i<chars.length;i++){
                index = chars[i] - 'a';
                if (node.nexts[index] == null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
        public void  delete(String word){
            if (search(word) != 0){//确定树中加入过才删除
                char[] chs= word.toCharArray();
                TrieNode node = root;
                node.pass--;
                int index= 0;
                for (int i=0;i<chs.length;i++){
                    index = chs[i] - 'a';
                    if ( --node.nexts[index].pass == 0){//当到节点的pass为0的时候，后面可以全部删除了
                        node.nexts[index] = null;
                        return;
                    }
                    node.end--; 
                }
            }
        }
    }
}