$$\color{Red}{Trie字符串统计 三种语言和HashMap的getOrDefault}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思考

• 插入函数
  在整个son[N][26]中，第0行类似表头，为0即不存在对应字母的表头结点
  每当idx产生赋值，即新建结点，代表对这个新的结点赋值了唯一对应的身份证号
  因为idx单调上升，所以不会产生冲突！而且每个结点唯一，才能真正查询到是否
  存在我们要搜寻的字符串，cnt数组存储这Ｎ长度的字符串

java hashmap

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static int n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static Map<String, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            if(s[0].equals("I")) map.put(s[1], map.getOrDefault(s[1], 0) + 1);
            else System.out.println(map.getOrDefault(s[1], 0));
        }
    }
}

java trie树

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010, n, idx;
    static int[][] son = new int[N][26];
    static int[] cnt = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void add(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];
        }
        cnt[p] ++;
    }

    static 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 cnt[p];
    }

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            String[] s = br.readLine().split(" ");
            String op = s[0];
            char[] str = s[1].toCharArray();
            if ("I".equals(op)) add(str);
            else System.out.println(query(str));
        }
    }
}

python3

N = int(1e5 + 10)
idx = 0
cnt = [0] * N
son = [[0 for x in range(26)] for y in range(N)]

def insert(s):
    global idx
    p = 0
    for i in range(len(s)):
        u = ord(s[i]) - ord('a')
        if not son[p][u]:
            idx += 1
            son[p][u] = idx
        p = son[p][u]
    cnt[p] += 1

def qurey(s):
    p = 0
    for i in range(len(s)):
        u = ord(s[i]) - ord('a')
        if not son[p][u]:
            return 0
        else:
            p = son[p][u]
    return cnt[p]

if __name__ == '__main__':
    n = int(input())
    while n:
        n -= 1
        op = input().split()
        if op[0] == 'I':
            insert(op[1])
        else:
            print(qurey(op[1]))

C++

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int son[N][26], idx, cnt[N];
char str[N];
//插入函数
//在整个son[N][26]中，第0行类似表头，为0即不存在对应字母的表头结点
//每当idx产生赋值，即新建结点，代表对这个新的结点赋值了唯一对应的身份证号
//因为idx单调上升，所以不会产生冲突！而且每个结点唯一，才能真正查询到是否
//存在我们要搜寻的字符串，cnt数组存储这Ｎ长度的字符串
void insert(char *str)
{
    int p = 0;
    for(int i=0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p] ++;
}
//查询函数
//当一个唯一结点在插入终结，cnt[p]++,对他唯一赋值
//当我们查询的时候，查询到对应P终结，即可通过cnt的值判断是否存在
//甚至可以判断数量(这个数量指的是完全相同字符串的数量)
int query(char *str)
{
    int p = 0;
    for(int i=0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u])  return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        char op[2];
        scanf("%s%s", op, str);
        if(*op == 'I')  insert(str);
        else            cout << query(str) << endl;
    }
    return 0;
}