题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla
import java.util.Scanner;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
String[] strs = new String[n];
sc.nextLine();
for (int i = 0; i < n; i) strs[i] = sc.nextLine();
TrieNode root = new TrieNode();
for (String word : strs) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i) {
int index = word.charAt(i) - ‘a’;
if (cur.son[index] == null) cur.son[index] = new TrieNode();
cur = cur.son[index];
}
cur.count++;
}

    for (int j = 0; j < m; j++) {
        String s = sc.nextLine();
        TrieNode cur = root;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (cur.son[index] == null) break;  // 两种情况 没有儿子 那么直接break 有儿子 
            // 可能这个点有前缀 也可能没有反正+ count (没有等于0就是了等于没加)
            count += cur.son[index].count;
            cur = cur.son[index];
        }
        System.out.println(count);
    }
}

}
class TrieNode{
TrieNode[] son = new TrieNode[26];
int count = 0; // 把string s 换成 count 因为可能有不止一个
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla