GPT的介紹

🧠 一句話總結：

字典樹是一種專門用來存很多字符串的“超級前綴樹”，查找某個字符串或前綴的時候，特別快！

---

?? 舉個生活例子（類比）：

你想做一個詞典（Dictionary），里面有這些單詞：

apple
app
april
bat
ball
banana

你現在想知道：

• “apple”在不在詞典里？ ?
• “app”是某個單詞的前綴嗎？?
• 有沒有以 “ba” 開頭的單詞？?

如果你把這些單詞一個個拿出來比，那太慢了。

于是我們把它們塞進一個神奇的數據結構：字典樹。

---

🌳 字典樹長啥樣？

我們用“樹”的形式來表示字符串的每個字母（從根節點一層一層往下走）：

           (根)/a/p/ \p   r/     \l       i/         \e           l另一邊：b/   \a     a/       \l         n/           \l             a\n\a

每個節點代表一個字母，每條路徑代表一個字符串

每個節點有cnt，表示以這個節點為結尾的字符串的個數

---

🚀 字典樹的速度怎么樣？

• 普通查找（字符串在數組里）時間是：O(字符串長度 × 數組長度)
• 字典樹查找時間是：O(字符串長度)，和多少單詞沒關系！

---

💡 形象一點說：

• 數組/哈希表：像是一頁一頁翻字典
• 字典樹：像是按字母順序直接走向目標

就像 Google 搜索你輸入 "ap"，它能秒給你推薦 "apple"、"app store"、"april" —— 這背后可能就是字典樹！

---

🧩 總結一張圖：

"apple", "app", "april" ==> 共享前綴 "ap"↓
Trie 就是把這些前綴共享，像搭積木一樣拼起來↓
節省空間 + 查詢高效

---

模板

N一般開到2e5+10就足夠了

0表示根節點 不存任何字符 是空節點

• Trie 根節點永遠不表示任何字母，根節點只是一顆“無名的樹根”
• 它是連接所有字母的“共同出發點”
• 它不存任何字符，也不是任何單詞的一部分

++idx表示給當前字符分配編號

     	[根0]/    \a        b↓        ↓p        a↓        ↓p        n↓        ↓l        a↓        ↓e        n↓a

const int N = 1e5 + 10; // 最大節點數（字符串數量×平均長度）
int son[N][26];        // 每個節點的26個子節點（用下標表示）
int cnt[N];             // cnt[i] 表示以 i 號節點結尾的單詞個數
int idx = 0;            // 當前用到的節點編號（0 是根）// 插入字符串
void insert(const string &s) {int p = 0;for (char c : s) {int u = c - 'a';if (!son[p][u]) son[p][u] = ++idx; // 創建新節點p = son[p][u];}cnt[p]++; // 這個節點是一個完整單詞的結尾
}
// 查詢字典樹中插入了幾個s
int query(const string& s) {int p = 0;for (int i = 0; i < s.size(); ++i) {int u = s[i] - 'a';if (son[p][u] == 0) {return 0;}p = son[p][u];}return cnt[p];
}

查詢是否存在以prefix 為前綴的字符串

bool startsWith(string prefix) {int p=0;for(auto c:prefix){int u=c-'a';if(son[p][u]==0) return 0;p=son[p][u];}return 1;   
}