avatar

Trie字符串统计

Trie字符串统计

存储字符串,快速存储字符串集合

高效存储和查找

特点:字母的个数不会很多

以单词的结尾要标记,用星号标记

定义子节点son[N][26] 存的是每个点的儿子 cnt[N] ,以当前这个点结尾的下标有多少个,idx当前用到了那个下标

模板

int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}



//java代码

题目

AcWing

  • 935 Trie字符串统计
  • 143 最大异或对

Ac935 Trie字符串统计

描述

维护一个字符串集合,支持两种操作:

  1. “I x”向集合中插入一个字符串x;
  2. “Q x”询问一个字符串在集合中出现了多少次。
解答
import java.io.*;

public class Main {

static final int N = 10010; //字符串最长为10000
static int[][] son = new int[N][26]; //每个点最多26个子节点
static int[] cnt = new int[N]; //统计次数
static int idx; //idx索引,唯一

public static void main(String[] args) throws Exception {
//只需要缓存读,输出问题不大
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//询问次数
int n = Integer.parseInt(br.readLine());
while(n-->0){
String[] ss = br.readLine().split(" ");
String o = ss[0];//操作,增加或是查询
String s = ss[1];
if(o.equals("I")){
insert(s);
}else{
int ans = query(s);
System.out.println(ans);
}
}
}

public static void insert(String s){
int p = 0;
for(int i=0;i<s.length();i++){
int u = s.charAt(i)-'a';
if(son[p][u]==0){
//没有这个点
son[p][u] = ++idx;
}

p = son[p][u];
}
//这里的p是最后的
cnt[p]++;
}

public static int query(String s){
int p = 0;
for(int i=0;i<s.length();i++){
int u = s.charAt(i)-'a';
if(son[p][u]==0){
return 0;
}
p = son[p][u];
}

return cnt[p];
}

}

Others

人无完人,何况是小白Chen我呢,文章难免会出现一些错误,若是读者们发现错误,可以评论或者联系我,Chen会尽力改正,给大家更优秀的博文。

文章作者: Chen
文章链接: https://vccyb.gitee.io/myblog/2020/03/24/Algorithm/articleM-18/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 东川
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论