[HiHoCoder]#1014:Trieツリー

時間制限:
10000ms
単一点時限:
1000ms
メモリの制限:
256MB
説明
HiさんとHoさんは良い友达で、情报化社会に生まれた彼らはプログラミングに大きな兴味を持って、彼らはお互いに助け合うことを约束して、プログラミングの学习の道の上でいっしょに进みます.
この日、彼らは辞書に出会ったので、HiさんはHoさんにその古典的な質問をしました.「Hoさん、私が与えた文字列ごとに、この辞書の中でこの文字列で始まるすべての単語を見つけることができますか?」
百戦錬磨のホーは答えた.「どうしてできないの.文字列を1つあげるたびに、辞書の中のすべての単語を順番に巡り、あなたがくれた文字列がこの単語の接頭辞ではないかをチェックします.」
Hiちゃんは笑って言いました:“あなた、やはり若すぎます!~もしこの辞書の中に10万の単語があるとしたら、私はあなたに1万回聞いて、あなたはどの年のどの月に行かなければなりませんか?”
Hoちゃんは頭を下げて計算して、その山の0を見て、すぐに自分が一生上に使うと感じました...
HiちゃんはHoちゃんの顔を見て、「知識のレベルを上げましょう.木のようなデータ構造を知っていますか」と笑い続けた.
Hoさんは考えて、「知っています~それは基礎的なデータ構造で、ここで言ったように!」と言いました.
Hiさんは満足そうにうなずいて、「じゃあ、辞書全体を木で表す方法を知っていますか」と言った.
Hoさんは首を横に振って自分が分からないことを示した.
ヒント1:Trieツリーの作成
「ほら、私たちは今このような木を手に入れました.では、もし私があなたに文字列apをあげたら、どうやってapで始まる単語を見つけますか?」Hiさんはまた学校のHoさんを受験し始めました.
「うん...すべての単語を一つ一つ巡る?」Hoちゃんはやはり自分が最初に出したアルゴリズムを忘れない.
「ばか!この木は白く建てられたのか!」HiちゃんはHoちゃんを教訓にして、「よく見て!」と続けた.
ヒント2:Trieツリーの使用方法
ヒント3:Trieツリーを作成するときに統計を同時に行う!
「じゃあ今!早くコードで実現しましょう!」Hiちゃんはこう言いました.
入力
入力された第1の動作は正の整数nであり、辞書のサイズを表し、その後n行、行ごとに単語を1つずつ(英単語であることは保証されていませんが、火星語の単語である可能性もありますよ)、単語は10個を超えない小文字の英字からなり、同じ単語が存在する可能性があります.この場合、それを異なる単語と見なすべきです.次の行為は正の整数mで、小Hi質問の次数を表し、その後m行、各行に1文字列、この文字列は10個を超えない小文字の英字からなります母の構成で、Hiちゃんの質問を表しています.
20%のデータではn,m<=10,辞書のアルファベットサイズ<=2である.
60%のデータのうちn,m<=1000,辞書のアルファベットサイズ<=5.
100%のデータでn,m<=10000000,辞書のアルファベットサイズ<=26.
本題は合格したデータ量でランキングしますよ～
しゅつりょく
小Hiの各問合せについて、小Hiで与えられた文字列を接頭辞とする辞書の単語の個数を表す整数Ansが出力される.
サンプル入力

5
babaab
babbbaaaa
abba
aaaaabaa
babaababb
5
babb
baabaaa
bab
bb
bbabbaab

サンプル出力

1
0
3
0
0

import java.util.Scanner;
public class Main {
  class Trie{
    int val;
    Trie next[];
    Trie(){
      val = 0;
      next = null;
    }
    public void init(){
      next = new Trie[26];
    }
  }
  Trie tr = new Trie();
  private void insert(String str){
    int i = 0;
    Trie foo =tr;
    while(i<str.length()){
      int idx = str.charAt(i)-'a';
      if(foo.next==null){
        foo.init();
      }
      if(foo.next[idx]==null){
        foo.next[idx] = new Trie();
        foo.next[idx].val++;
      }else{
        foo.next[idx].val++;
      }
      foo = foo.next[idx];
       i++;
    }
  }
  
  private int query(String str){
    Trie foo = tr;
    int i = 0;
    while(i<str.length()){
      int idx = str.charAt(i) -'a';
      if(foo.next ==null||foo.next[idx] ==null) return 0;
      foo = foo.next[idx];
      i++;
    }
    return foo.val;
  }
  
  public static void main(String args[]){
    Main main = new Main();
/*    Scanner sc = null;
    try {
      sc = new Scanner(new FileInputStream("C:\\Users\\ddguo\\Desktop\\test.txt"));
    } catch (FileNotFoundException e) {
      e.printStackTrace();
    }*/
    Scanner sc = new Scanner(System.in);
        
    int initTrie = sc.nextInt();
    while(initTrie-->0){
      main.insert(sc.next());
    }
    int queryInt = sc.nextInt();
    while(queryInt-->0){
      System.out.println(main.query(sc.next()));
    }
    sc.close();
  }
}