This is Trie Tree,Dictionary tree, is used to search the words, save the words… It’s a words’ set.
维护一个字符串集合，支持两种操作：
“I x”向集合中插入一个字符串x； “Q x”询问一个字符串在集合中出现了多少次。 共有N个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入格式 第一行包含整数N，表示操作数。
接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。
输出格式 对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。
每个结果占一行。
数据范围 1≤N≤2∗104 输入样例： 5 I abc Q abc Q ab I ab Q ab 输出样例： 1 0 1
Like a Dictionary to set the words. (failed upload the pic) The module :
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static PrintWriter pw = new PrintWriter(System.out); static int N = 100010; static int son[][] = new int[N][26], cnt[] = new int[N], idx; //son is next point, cnt is that point if the end. public 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]++; } public 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) throws IOException { int n = Integer.parseInt(br.readLine()); while (n-- > 0) { String input[] = br.readLine().split(" "); if (input[0].equals("Q")) pw.println(query(input[1])); else insert(input[1]); } pw.flush(); } }