1.Tire 字符串統計

#include<algorithm>
#include<cstring>
#include<iostream>using namespace std;const int N=100010;
int son[N][26];//至多 N 層，每一層至多 26 個節點（字母）
int cnt[N];//字符串至多 N 個，標記每個字符串的最后一個字母，
//統計出現次數
int idx;//用到的節點的總數
char str[N];//單次輸入的字符串void insert(char str[]){int p=0;//根節點for(int i=0;str[i];i++){//字符串的每一個字母分別存在每一層int u=str[i]-'a';//把 a-z 映射到 0-25if(!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];
}int main(){int n;cin>>n;while(n--){char op[2];cin>>op>>str;if(op[0]=='I'){insert(str);}else{printf("%d\n",query(str));}}return 0;
}