AcWing 835. Trie字符串统计(Java)
原题链接
简单
作者:
火球大的脸盆
,
2022-07-07 15:56:22
,
所有人可见
,
阅读 125
import java.io.*;
public class Main {
public static int N = 100005, idx; //idx是每个结点的唯一标识,根结点root是0
public static int[] cnt = new int[N]; //cnt[p]是以p节点为结尾的字符串的个数
public static int[][] son = new int[N][26]; //son[p][u]标识了p结点的子结点u是否存在
public static void insert(char[] str) {
int p = 0;
for (int i = 0; i < str.length; i++) { //Java的字符数组末尾不是'\0',所以要用lenth来判断结束。
int u = str[i] - 'a'; //将字母映射成阿拉伯数字0-25。
if (son[p][u] == 0) son[p][u] = ++idx; //如果p结点没有u这个子结点,那么人为创建联系,即加上idx。
p = son[p][u]; //p指向下一个结点,即子结点。
}
cnt[p]++; //插入完毕,以p结点为结尾的字符串数量++。
}
public 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结点没有子结点u,那么一定找不到了,直接返回0。
p = son[p][u];
}
return cnt[p];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
while (0 != n--) {
String[] s = br.readLine().split(" ");
if ("I".equals(s[0])) insert(s[1].toCharArray());
else if ("Q".equals(s[0])) {
bw.write(query(s[1].toCharArray()) + "\n");
bw.flush();
}
}
}
}