【快速幂，字符串hash，前缀字典树】

package com.test.autimatic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class PowAndHashString {

    public static void main(String[] args) {
        PowAndHashString string = new PowAndHashString();
        System.out.println(string.getPow(3,1));
        //--test
        System.out.println(1e5);
        //--hashString
        string.stringHash("asdfcfdgrasdfcvgfliuoiuliuoiuiwernhchzh",5);
    }

    
    public int getPow(int p,int time) {
        int temp = 1;
        while (time > 0){
            if((time & 1) == 1){
                temp *= p;
            }
            p *= p;
            time >>= 1;
        }
        return temp;
    }

    
    public void stringHash(String hash,int len){
        long[] hashS = new long[hash.length() + 1];
        long[] hashE = new long[hash.length() + 1];
        //解决冲突，散列分布值
        hashS[0] = 1;int mod = 131;
        for (int i = 0; i < hash.length(); i++) {
            hashS[i + 1] = hashS[i] * mod;
            hashE[i + 1] = hashE[i] * mod + hash.charAt(i);
        }
        //获取元素---
        List result = new ArrayList<>(16);
        Map map = new HashMap<>(16);
        for (int i = 1,j = i + len - 1; j < hash.length(); i++, j++) {
            long key = hashE[j] - hashE[i - 1] * hashS[len];
            Integer val = map.getOrDefault(key, 0);
            if(val == 1){ result.add(hash.substring(i-1,j)); }
            map.put(key,val + 1);
        }
        System.out.println(result);
    }

    
    public static class Trie{
        public Trie[] children;
        public boolean end;

        public Trie() {
            children = new Trie[26];
            end = false;
        }

        public Trie(Trie[] children, boolean end) {
            this.children = children;
            this.end = end;
        }

        
        public void insert(String word){
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                if(node.children[word.charAt(i) - 'a'] == null){
                    node.children[word.charAt(i) - 'a'] = new Trie();
                }
                node = node.children[word.charAt(i) - 'a'];
            }
            node.end = true;
        }

        
        public Trie find(String temp){
            Trie node = this;
            for (int i = 0; i < temp.length(); i++) {
                if(node.children[temp.charAt(i) - 'a'] == null){
                    return null;
                }
                node = node.children[temp.charAt(i) - 'a'];
            }
            return node;
        }

        
        public boolean isEnds(String end){
            Trie trie = find(end);
            return trie != null && trie.end;
        }

        
        public boolean prefis(String prefix){
            return find(prefix) != null;
        }

    }


}