AcWing 835. Trie字符串统计_Java含注释
原题链接
简单
作者:
FayunYm
,
2020-12-26 14:27:54
,
所有人可见
,
阅读 356
import java.util.Scanner;
public class Trie {
static final int M = 100_010; //字符串总长度加一起不超过100_000,因此M行肯定够用
static int[][] son = new int[M][26]; //son指示寻找子节点应去哪(如son[1][2]=5指示了寻找其c的子节点要去第5层(0为最上层)
//son最好画图理解
static int[] cnt = new int[M]; //存储某个结点对应的字符串个数
static int idx; //结点数,为0指示空结点或根节点
static void insert(String s) {
int p = 0; //从第0层开始查询
for(int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a'; //该字符应去哪一列查找
if(son[p][u] == 0) {
son[p][u] = ++idx; //字符串该字符没有对应的结点,则创建结点(第++idx个结点即第++idx层去查找)
}
p = son[p][u]; //到下一个结点
}
cnt[p] ++; //该结点是末节点,对应字符串数量+1
}
/* 插入看懂了,查询自然就懂了 */
static int query(String s) {
int p = 0;
for(int i = 0; i< s.length(); i++) {
int u = s.charAt(i) - 'a';
if(son[p][u] ==0) return 0;
p = son[p][u];
}
return cnt[p];
}
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine(); //空行吃掉,不然有错
while (n-- != 0) {
String[] op = sc.nextLine().split(" ");
if(op[0].equals("I")) {
insert(op[1]);
} else System.out.println(query(op[1]));
}
}
}