算法1：

注意：
① 对于son[p][] 的理解非常关键，p说指向的每一行是每个不同的字符串前缀的地址。
例如：插入 “abcd” “acd” “bcd”
son[0] : “” 为前缀的地址
son[1] ：”a” 为前缀的地址
son[2] ：”ab” 为前缀的地址
son[3] ：”abc” 为前缀的地址
son[4] ：”abcd” 为前缀的地址
son[5] ：”ac” 为前缀的地址
son[6] ：”acd” 为前缀的地址
son[7] ：”b” 为前缀的地址
son[8] ：”bc” 为前缀的地址
son[9] ：”bcd” 为前缀的地址

//插入
private static void insert(char[] str) {
    // 指向str
    int p = 0;
    for(int i = 0; i < str.length; i++){
        int u = str[i] - 'a';
        // idx是全局变量一直在++，说明对于新的字符串，要给其分配一个地址（即idx）
        // son[p][] 指str[0]- str[p-1]子串组成的前缀，以这个为前缀的字符串存在的位置。这个前缀后面-个字母可能有26个选择，
        // son[p][u] 存储值是指 str[0]- str[p-1]子串组成的前缀，第p个字符是u时候的地址，这个地址不一定是son[p+1],
        if(son[p][u] == 0) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;// for结束时候都要执行的是p = son[p][u]; 所以cnt[p] 而不是cnt[idx]

}

//查找字符串出现的次数
private static int query(char[] str) {
    int p=0;
    for(int i=0;i<str.length;i++){
        int u=str[i]-'a';
        // ==0说明之前没开辟过这个前缀
        if(son[p][u]==0) return 0;
        //开辟过这个前缀那么找到这个前缀的地址
        p=son[p][u];
    }
    return cnt[p];
}

// 完整代码
import java.util.Scanner;

public class Main {

    private static int N=100010;
    private static int son[][]=new int[N][26];//每行代表一个前缀的地址
    private static int cnt[]=new int[N];//以当前这个前缀结束的单词有多少个
    private static char str[]=new char[N];
    // idx一直在++，没有归零过，其为每个不同的字符子串开辟一个新的地址。
    private static int idx;//当前用的的哪个下标，下标0：既是根节点又是空节点。


    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        while (n-->0){
            String op=scanner.next();
            String str=scanner.next();
            if("I".equals(op)){
                insert(str.toCharArray());
            }else if("Q".equals(op)){
                System.out.println(query(str.toCharArray()));
            }
        }
    }

    //插入
    private static void insert(char[] str) {
        // 指向str
        int p = 0;
        for(int i = 0; i < str.length; i++){
            int u = str[i] - 'a';
            // idx是全局变量一直在++，说明对于新的字符串，要给其分配一个地址（即idx）
            // son[p][] 指str[0]- str[p-1]子串组成的前缀，以这个为前缀的字符串存在的位置。这个前缀后面-个字母可能有26个选择，
            // son[p][u] 存储值是指 str[0]- str[p-1]子串组成的前缀，第p个字符是u时候的地址，这个地址不一定是son[p+1],
            if(son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;// for结束时候都要执行的是p = son[p][u]; 所以cnt[p] 而不是cnt[idx]

    }

    //查找字符串出现的次数
    private static int query(char[] str) {
        int p=0;
        for(int i=0;i<str.length;i++){
            int u=str[i]-'a';
            // ==0说明之前没开辟过这个前缀
            if(son[p][u]==0) return 0;
            //开辟过这个前缀那么找到这个前缀的地址
            p=son[p][u];
        }
        return cnt[p];
    }
}