2、Trie字符串统计&最大异或对

AcWing 835. Trie字符串统计

AcWing 143. 最大异或对

Leetcode 720. 词典中最长的单词

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.Trie_Zifu();
    }

    int N = 200010;
    int son[][] = new int[N][26];
    int count[] = new int[N];
    int idx = 0;//idx相当于地址码,唯一的对应一个单词

    void insert(char[] str) {
        int p = 0;
        for (int i = 0; i < str.length; i++) {
            int u = str[i] - 'a';
            if (son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
        count[p]++;
    }

    int query(char[] str) {
        int p = 0;
        for (int i = 0; i < str.length; i++) {
            int u = str[i] - 'a';
            if (son[p][u] == 0) return 0;
            p = son[p][u];
        }
        return count[p];
    }

    void Trie_Zifu() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            String s0 = scanner.next();
            String s1 = scanner.next();
            if (s0.equals("I")) {
                insert(s1.toCharArray());
            }
            if (s0.equals("Q")) {
                System.out.println(query(s1.toCharArray()));
            }
        }
    }
}

import java.io.*;
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.Trie_Zifu();
    }

    int M = 3000000;
    int N = 100010;
    int son[][] = new int[M][2];
    int[] a = new int[N];
    int idx = 0;//idx相当于地址码,唯一的对应

    void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int s = son[p][x >> i & 1];//先找出son[][]对应的值
            if (s == 0) s = ++idx;//开辟新的分支
            p = son[p][x >> i & 1] = s;//更新一下
        }
    }

    int query(int x) {
        int res = 0, p = 0;
        for (int i = 30; i >= 0; i--) {
            int s = x >> i & 1;
            int f_s = (s == 0) ? 1 : 0;
            //如果存在相反的分支
            if (son[p][f_s] != 0) {
                res += 1 << i;
                p = son[p][f_s];
            } else p = son[p][s];
        }
        return res;
    }

    void Trie_Zifu() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), max = 0;
        for (int i = 0; i < n; i++) insert(a[i] = scanner.nextInt());
        for (int i = 0; i < n; i++) max = Math.max(max, query(a[i]));
        System.out.println(max);
    }
}

//词典中最长的单词
class Solution {
    int N = 10010;
    int[][] pp = new int[N][26];
    int count[] = new int[N];
    int idx = 0;

    void insert(char[] str) {
        int p = 0;
        for (int i = 0; i < str.length; i++) {
            int u = str[i] - 'a';
            if (pp[p][u] == 0) pp[p][u] = ++idx;
            p = pp[p][u];
        }
        count[p]++;
    }

    int query(char []str) {
        int p = 0;
        for (int i = 0; i < str.length; i++) {
            int u = str[i] - 'a';
            if (pp[p][u] == 0) return 0;
            p = pp[p][u];
        }
        return count[p];
    }

    public String longestWord(String[] words) {
        for (int i = 0; i < words.length; i++) {
            insert(words[i].toCharArray());
        }
        //Arrays.sort(words);
        int max=0;
        String max_s="";
        for (int i = 0; i < words.length; i++) {
            if(son_has_occ(words[i])){
                if(words[i].length()>max){
                    max=words[i].length();
                    max_s=words[i];
                }
                if(words[i].length()==max){
                    max_s=max_s.compareTo(words[i])<0?max_s:words[i];
                }
            }
        }
        return max_s;
    }
    boolean son_has_occ(String s){
        char []ss=s.toCharArray();
        for (int i = 1; i < ss.length; i++) {
            String co= s.substring(0,i);
            if(query(co.toCharArray())==0){
                return false;
            }
        }
        return true;
    }
}