题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
import java.util.*;
public class Main {
static int N=100010;
static int[][]son=new int[N][26];
static int[]cnt=new int[N];
static int n;
static int idx;//当前创建的节点的序号
static void insert(String str){
int p=0;//当前所指的节点的序号
for(int i=0;i<str.length();i++){
int u=str.charAt(i)-'a';
if(son[p][u]==0){//当前节点还没有创建
son[p][u]=++idx;
}
p=son[p][u];//更新当前的指针
}
//字符串的最后叶节点做标记
cnt[p]++;
}
static int query(String str){
int p=0;
for(int i=0;i<str.length();i++){
int u=str.charAt(i)-'a';
if(son[p][u]==0){
return 0;
}
p=son[p][u];
}
return cnt[p];
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
while (n--!=0){
String s=sc.next();
String str=sc.next();
if(s.equals("I")){
insert(str);
}else{
System.out.println(query(str));
}
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla