AcWing 835. Trie字符串统计(JAVA)
原题链接
简单
作者:
鼠鼠我
,
2021-01-30 23:07:10
,
所有人可见
,
阅读 389
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
//Trie树 trie 高效存储+查询字符串
//Trie树中有个二维数组son[N][26],表示当前结点的儿子,
//如果没有的话,可以等于++idx。Trie树本质上是一颗多叉树,
//对于字母而言最多有26个子结点。所以这个数组包含了两条信息。
//比如:son[1][0]=2表示1结点的一个值为a的子结点为结点2。
//如果son[1][0] = 0,则意味着没有值为a子结点。
//这里的son[N][26]相当于链表中的ne[N]。
public class Main {
static int N = 100010;
static int[][] son = new int[N][26];//son[1][0]=2表示1结点的一个值为a的子结点为结点2。
static int[] cnt = new int[N];//将该字符串分配的一个树结构中,以下标来记录每一个字符的位置。方便之后的插入和查找。
static int idx;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String s[] = br.readLine().split("\\s+");
int n = Integer.parseInt(s[0]);
for(int i=0;i<n;i++)
{
String ss[] = br.readLine().split("\\s+");
String c = ss[0];
String x = ss[1];
if(c.equals("I"))
insert(x);
else {
System.out.println(query(x));
}
}
}
static void insert(String x)//插入x字符串
{
char[] str = x.toCharArray();
int p = 0;//初始根结点为0
for(int i=0;i<str.length;i++)
{
int u = str[i]-'a';
if(son[p][u]==0) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;//以这个字符结束的字符串数量+1
}
static int query(String x)//查找
{
char[] str = x.toCharArray();
int p = 0;
for(int i=0;i<str.length;i++)
{
int u = str[i] - 'a';
if(son[p][u]==0)
return 0;
p = son[p][u];
}
return cnt[p];
}
}