AcWing 142. 前缀统计
原题链接
简单
作者:
ACSaber
,
2020-11-30 11:31:37
,
所有人可见
,
阅读 409
import java.util.*;
import java.io.*;
class Main {
static int N = 1000009;
static int[][] trie = new int[N][26];
static int[] count = new int[N];
static int idx = 0;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = reader.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
for (int i = 1; i <= n; i++) {
String str = reader.readLine();
insert(str);
}
for (int i = 1; i <= m; i++) {
String str = reader.readLine();
writer.write(preCnt(str) + " ");
writer.write("\n");
}
reader.close();
writer.flush();
writer.close();
}
private static void insert(String s) {
int p = 0;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (trie[p][u] == 0) trie[p][u] = ++idx;
p = trie[p][u];
}
count[p]++;
}
private static int preCnt(String s) {
int ans = 0;
int p = 0;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (trie[p][u] != 0) {
p = trie[p][u];
ans += count[p];
} else {
break;
}
}
return ans;
}
}