AcWing 835. Trie字符串统计
原题链接
简单
作者:
没有你哪有我
,
2022-02-13 13:00:42
,
所有人可见
,
阅读 152
import java.util.*;
import java.io.*;
/**
* Trie树
*/
public class Main {
static int N = 100000 + 10;
// 孩子节点
static int[][] son = new int[N][26];
// cnt[i]的含义:表示以节点i结尾的字符串的个数
static int[] cnt = new int[N];
// 下标从0开始,根节点既是开始节点,也是0,本身没有值
static int idx;
static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
public static void insert(char[] c) {
// 从根节点开始遍历
int p = 0;
int n = c.length;
for (int i = 0; i < n; i ++ ) {
// 将z-a的字母Asclli码映射成从0-25
int u = c[i] - 'a';
if (son[p][u] == 0) son[p][u] = ++idx;
p = son[p][u];
}
// 此时p已经到了最后一个字符,数量++
cnt[p]++;
}
public static int query(char[] c) {
int p = 0;
int n = c.length;
for (int i = 0 ; i < n; i++ ) {
int u = c[i] - 'a';
if (son[p][u] == 0) {
// 不存在,直接返回0
return 0;
}
// son[p][u] > 0说明存在该孩子节点,则递归往后找
p = son[p][u];
}
// 此时p已经走到当前字符串的最后一个字符位置,返回以该前缀结尾的字符串个数
return cnt[p];
}
public static void main(String[] args) throws Exception{
int n = Integer.parseInt(r.readLine());
while (n -- > 0) {
String[] s = r.readLine().split(" ");
String op = s[0];
char[] x = s[1].toCharArray();
if (op.equals("I")) {
insert(x);
} else {
w.write(query(x) + "\n");
}
}
// 刷新缓冲
w.flush();
}
}