- 【用途】：給定多個字串，接著多次詢問某字串有沒有出現過。
- 【變化】01字典樹：每一層代表一個bit 或 true/false，用於查找是否出現過。
- 【練習】HDU 4852 Xor Sum【題解】
- 【練習】Codeforces I. Interactive Casino
- 【練習】Google Code Jam 2019 Round 1A C Alien Rhyme【題解】
- 關於字串的一些名詞：字串 string s;
- 字串長度：s.size(); 或 strlen(s);
- 子字串 (substring)：字串 s 中一段連續的字串。
- 子序列 (subsequence)：字串 s 中一段可不連續的字串，但出現順序必須和原字串相同。
- 前綴(prefix)：從頭開始的一段substring。
- 後綴(suffix)：到結尾的一段substring。
【字典樹實作】
struct TrieNode {
int nxt[26]; //遇到a~z時的節點編號(idx)
int cnt; //以此結尾的字串個數
} node[1000005];
int idx = 2; //root = 1
【加入一個字串】
voide insert(string s){
int cur = 1; //從root開始
for(auto i:s) {
if(node[cur].nxt[i-’a’] == 0){
node[cur].nxt[i-’a’] = idx; \\開一個新的node
cur = idx;
idx++;
}
else {
cur = node[cur].nxt[i-’a’];
}
}
node[cur].cnt++;
}
【查詢一個字串】
int query(string s){
int cur = 1;
for(auto i:s) {
if(node[cur].nxt[i-’a’] == 0){
return 0;
}
else {
cur = node[cur].nxt[i-’a’];
}
}
return node[cur].cnt;
}
