临时想的一种结构
class Node {
int endNum = 0;
Node[] kids = new Node[26];
}
刚开始以为会爆内存
最后居然还ac了。。。
请多指教
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
Node tree = new Node();
while (n-- > 0) {
String str = sc.next();
int idx = -1;
Node o = tree;
while (++idx < str.length()) {
int x = str.charAt(idx) - 'a';
if (o.kids[x] == null) o.kids[x] = new Node();
o = o.kids[x];
}
o.endNum++;
}
while (m-- > 0) {
String str = sc.next();
int res = 0, idx = -1;
Node o = tree;
res += o.endNum;
while (++idx < str.length()) {
int x = str.charAt(idx) - 'a';
if (o.kids[x] == null) break;
o = o.kids[x];
res += o.endNum;
}
System.out.println(res);
}
}
}
class Node {
int endNum = 0;
Node[] kids = new Node[26];
}