基础算法-字典树
Trie
主要是需要一个二维数组int[x][y]保存字典树。用一个一维数组保存该节点是否是字符串的结尾。
例题: https://www.acwing.com/problem/content/837/
代码:
import java.io.*;
public class Main{
private static int N = 100010;
private static int[][] trie = new int[N][26];
private static int idx = 0;
private static int[] flag = new int[N];
private static void insert(String str){
int q = 0;
for(int i = 0 ; i < str.length(); i++){
int v = str.charAt(i) - 'a';
if(trie[q][v] == 0){
trie[q][v] = ++idx;
q = idx;
}else{
q = trie[q][v];
}
}
flag[q] ++;
}
private static int query(String str){
int q = 0;
for(int i = 0 ;i < str.length(); i++){
int v = str.charAt(i) - 'a';
if(trie[q][v] == 0){
return 0;
}else{
q = trie[q][v];
}
}
return flag[q];
}
public static void main(String[] args) throws Exception{
var in = new BufferedReader(new InputStreamReader(System.in));
var out = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(in.readLine());
while(n > 0){
n--;
String[] line = in.readLine().split(" ");
String op = line[0];
String str = line[1];
if(op.equals("I")){
insert(str);
}else{
out.write(String.valueOf(query(str)) + "\n");
}
}
in.close();
out.close();
}
}