题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

O(n)

参考文献

Java 代码

import java.util.Scanner;
import java.lang.Math;
import java.lang.Character;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
static class StrNode{
final char val;
Map[HTML_REMOVED] children = new HashMap[HTML_REMOVED](); //所有孩子节点
public StrNode(char v){
val = v;
}
boolean isEnd = false; //这个字符是不是某个单词的结尾
int endCnt = 0 ; //以这个字符为结尾的单词个数
}

static Scanner sc   = new Scanner(System.in);
static StrNode root = new StrNode('#');

static void insert(char[] strArr){
    StrNode node = root;
    for(char c : strArr){
        StrNode child = node.children.get(c);
        if(child == null){
            child = new StrNode(c);
            node.children.put(c,child);
        }
        node = child;
    }
    node.isEnd = true;
    node.endCnt++;
}

static int search(char[] strArr){   
    int res =0 ;
    StrNode node = root;
    for(char c : strArr){
        StrNode child = node.children.get(c);
        if(child == null){
           break;
        }
        node = child;
        res += node.endCnt;
    }
    return res;
}

public static void main(String []args){
    int N = sc.nextInt();
    int M = sc.nextInt();
    while(N-- >0){
        insert(sc.next().toCharArray());
    }
    while(M-- > 0){
        System.out.println(search(sc.next().toCharArray()));
    }
}

}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla