Untitled

class Trie {
    static final int MAX_NODE = 350000;
    
    class Node {
        int cnt;
        int[] child;
        
        Node() {
            cnt = 0;
            child = new int[26];  // Mỗi phần tử đại diện cho một chữ cái
            for (int i = 0; i < 26; ++i) {
                child[i] = -1;
            }
        }
    }
    
    Node[] nodes = new Node[MAX_NODE];
    int nodeNum;

    public Trie() {
        init();
    }
    
    int newNode() {
        nodes[nodeNum] = new Node();
        return nodeNum++;
    }
    
    int calc(String str, int id, int command) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '?') {
                for (int j = 0; j < 26; ++j) {
                    if (nodes[id].child[j] != -1) {
                        count += calc(str.substring(i + 1), nodes[id].child[j], command);
                    }
                }
                return count;
            } else if (nodes[id].child[c - 'a'] == -1) {
                return count;
            } else {
                id = nodes[id].child[c - 'a'];
            }
        }
        count += nodes[id].cnt;
        nodes[id].cnt *= command;
        return count;
    }
    
    void init() {
        nodeNum = 0;
        newNode();
    }
    
    int add(String str) {
        int id = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (nodes[id].child[c - 'a'] == -1) {
                nodes[id].child[c - 'a'] = newNode();
            }
            id = nodes[id].child[c - 'a'];
        }
        return ++nodes[id].cnt;
    }
    
    int remove(String str) {
        return calc(str, 0, 0);
    }
    
    int search(String str) {
        return calc(str, 0, 1);
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        
        // Thêm từ vào Trie
        System.out.println(trie.add("apple"));  // Kết quả: 1
        System.out.println(trie.add("apple"));  // Kết quả: 2
        System.out.println(trie.add("app"));    // Kết quả: 1
        
        // Tìm kiếm từ
        System.out.println(trie.search("app")); // Kết quả: 1
        
        // Xóa từ khỏi Trie
        System.out.println(trie.remove("apple")); // Kết quả: 2
    }
}