题目描述
统计字符串的个数
算法
思想:字典树存储
存储:
son[N][26] // 存储字典树结构,具体的存储的值是存储下一个字符所在的位置
以链表的形式进行连接
具体代码
import java.util.*;
import java.io.*;
public class Main {
static int N = 100010;
static int[][] son = new int[N][26];
static int idx = 0;
static int[] cnt = new int[N];
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
int n = Integer.parseInt(line[0]);
for (int i=0; i<n; i++) {
line = reader.readLine().split(" ");
String op = line[0];
String s = line[1];
if ("I".equals(op)) insert(s);
else System.out.println(query(s));
}
}
private static void insert(String s) {
int p = 0;
for (int i=0; i<s.length(); i++) {
int u = s.charAt(i) - 'a';
if (son[p][u] == 0) son[p][u] = ++idx; // 下一个字符安排的位置
p = son[p][u];
}
cnt[p]++;
}
private 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];
}
}