835. 字串統計（Trie樹模板題）-有解無憂

維護一個字串集合，支持兩種操作：

“I x”向集合中插入一個字串x；
“Q x”詢問一個字串在集合中出現了多少次，

共有N個操作，輸入的字串總長度不超過 $10^{5}$

輸入格式

第一行包含整數N，表示運算元，

接下來N行，每行包含一個操作指令，指令為”I x”或”Q x”中的一種，

輸出格式

對于每個詢問指令”Q x”，都要輸出一個整數作為結果，表示x在集合中出現的次數，

每個結果占一行，

資料范圍

$1 \leq N \leq 2 * 10^{4}$

輸入樣例：

5
I abc
Q abc
Q ab
I ab
Q ab

輸出樣例：

1
0
1

import java.util.Scanner;

public class Main{
        static final int max=100005;
        static int son[][]=new int[max][26];//son陣列存盤樹節點；
        static int cnt[]=new int[max];      //cnt[i]存盤以下標i為結點的字串的數量；
        static int idx;                     //idx表示當前用到了那個下標,下標是0的點既是根節點又是空節點
        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];
                }
                cnt[p]++;
        }
        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];
        }
         public static void main(String[] args) {
                 Scanner scan=new Scanner(System.in);
                 int n=scan.nextInt();
                 while(n-->0){
                         String s=scan.next();
                         if(s.equals("I")){
                                 String str=scan.next();
                                 insert(str);
                         }
                         else{
                                 String str=scan.next();
                                 System.out.println(query(str));
                         }
                 }
        }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102324.html

標籤：其他

上一篇：《演算法》筆記 17 - 資料壓縮

下一篇：Trie樹模板