ปูพื้นฐาน

ไทร: ทำให้คำถามเรื่องส่วนหัวมีราคาเท่าความยาวคำถาม ไม่ว่าคลังจะใหญ่แค่ไหน

โครงสร้างที่คนมองว่าไว้เก็บคำ แต่ของจริงคือแผนที่ของสถานะ บทนี้ให้ทั้งการใช้แบบตรงไปตรงมา การพลิกไปใช้กับตัวเลขฐานสอง และวิธีคำนวณหน่วยความจำก่อนตัดสินใจใช้ ซึ่งเป็นขั้นที่คนข้ามแล้วตกทีหลัง

ปัญหาที่บทนี้แก้

เวลามีคำอยู่เป็นหมื่นเป็นแสนคำ แล้วต้องถามซ้ำ ๆ ว่า "คำนี้อยู่ในคลังไหม" หรือ "มีกี่คำในคลังที่เป็นส่วนหัวของสตริงนี้" การไล่เทียบทีละคำจะเป็น จำนวนคำ × ความยาว ต่อหนึ่งคำถาม ซึ่งช้าเกินไปทันทีที่คำถามเยอะ

ไทร (trie) แก้ปัญหานี้ด้วยการเอาคำทั้งหมดมาซ้อนกันเป็นต้นไม้ตามส่วนหัวที่ใช้ร่วมกัน ค่าใช้จ่ายของคำถามหนึ่งคำถามจะเหลือแค่ความยาวของสตริงที่ถาม ไม่เกี่ยวกับว่าคลังใหญ่แค่ไหนเลย

โครงสร้างที่ต้องเห็นในหัวก่อน

ปมรากคือสตริงว่าง ปมลูกของปม p คือ p ที่ต่อท้ายด้วยหนึ่งตัวอักษร ดังนั้นปมหนึ่งปมคือคำนำหน้าหนึ่งอัน และเส้นทางจากรากลงมาถึงปมคือการสะกดคำนำหน้านั้น ปมที่เป็นจุดจบของคำจริง ๆ ในคลังจะติดธงไว้

ลองเอง · พิมพ์ให้สั้นที่สุดที่ยังชี้คำเดียวได้

สังเกตว่าจำนวนคำที่ยังเข้าได้ ลดลงเรื่อย ๆ ตามที่พิมพ์ ตัวเลขนั้นแหละคือของที่ควรเก็บไว้ที่ปมของไทร

โจทย์ฝึกข้อที่ 1 · นับส่วนหัวที่อยู่ในคลัง

ให้คำในคลัง n คำ แล้วมีคำถาม q ข้อ แต่ละข้อให้สตริงมาหนึ่งตัว ตอบว่ามีกี่คำในคลังที่เป็นส่วนหัวของสตริงนั้น (คำในคลังซ้ำกันได้)

เฉลยข้อที่ 1

// นับว่าในคลัง มีกี่คำที่เป็นส่วนหัวของสตริงคำถาม  (ตอบทุกคำถามในเวลารวมเชิงเส้น)
#include <bits/stdc++.h>
using namespace std;
struct Node { int ch[26]; int words; Node() { memset(ch, -1, sizeof ch); words = 0; } };
vector<Node> T;
int newNode() { T.push_back(Node()); return (int)T.size() - 1; }

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    T.reserve(1 << 20); newNode();
    for (int i = 0; i < n; i++) {
        char buf[1005]; scanf("%s", buf);
        int cur = 0;
        for (char* p = buf; *p; p++) {
            int k = *p - 'a';
            if (T[cur].ch[k] < 0) T[cur].ch[k] = newNode();
            cur = T[cur].ch[k];
        }
        T[cur].words++;                       // ปมนี้เป็นจุดจบของคำในคลังหนึ่งคำ
    }
    while (q--) {
        char buf[1005]; scanf("%s", buf);
        int cur = 0; long long ans = 0;
        for (char* p = buf; *p && cur >= 0; p++) {
            cur = T[cur].ch[*p - 'a'];
            if (cur < 0) break;
            ans += T[cur].words;              // ทุกปมที่เดินผ่านคือส่วนหัวหนึ่งอัน
        }
        printf("%lld\n", ans);
    }
}

โจทย์ฝึกข้อที่ 2 · คู่ที่ให้ค่า XOR มากที่สุด

ให้จำนวนเต็มไม่ติดลบ n ตัว หาคู่ที่ a XOR b มากที่สุด (XOR อ่านว่า "เอ็กซ์ออร์" คือการเทียบทีละบิต ได้ 1 เมื่อสองบิตต่างกัน)

เฉลยข้อที่ 2

// คู่ที่ให้ค่า XOR มากที่สุด  ใช้ไทรฐานสอง เดินจากบิตสูงลงบิตต่ำ
#include <bits/stdc++.h>
using namespace std;
const int BITS = 30;
struct Node { int ch[2]; Node() { ch[0] = ch[1] = -1; } };
vector<Node> T;
int newNode() { T.push_back(Node()); return (int)T.size() - 1; }

void insert(int v) {
    int cur = 0;
    for (int b = BITS; b >= 0; b--) {
        int k = (v >> b) & 1;
        if (T[cur].ch[k] < 0) T[cur].ch[k] = newNode();
        cur = T[cur].ch[k];
    }
}
int bestAgainst(int v) {
    int cur = 0, res = 0;
    for (int b = BITS; b >= 0; b--) {
        int k = (v >> b) & 1;
        if (T[cur].ch[k ^ 1] >= 0) { res |= 1 << b; cur = T[cur].ch[k ^ 1]; }  // ได้บิตนี้เป็นหนึ่ง
        else cur = T[cur].ch[k];                                               // จำใจเดินทางเดียวที่มี
    }
    return res;
}
int main() {
    int n; scanf("%d", &n);
    T.reserve(32 * n + 8); newNode();
    vector<int> a(n);
    for (auto& v : a) scanf("%d", &v);
    int ans = 0;
    insert(a[0]);
    for (int i = 1; i < n; i++) { ans = max(ans, bestAgainst(a[i])); insert(a[i]); }
    printf("%d\n", ans);
}

ทางที่คนคิดถึงก่อน · ยัดคำนำหน้าทุกอันลงตารางแฮช

ก่อนจะรู้จักไทร คนส่วนใหญ่คิดออกอีกทางหนึ่งก่อน และทางนั้นถูกจริงและเขียนสั้นกว่ามาก คือถ้าคำถามคือ "มีคำในคลังกี่คำที่เริ่มด้วยข้อความนี้" ก็เอาคำนำหน้าทุกอันของทุกคำ ไปยัดลงตารางแฮชพร้อมตัวนับไว้เลย แล้วตอบคำถามด้วยการค้นหาหนึ่งครั้ง

คำยาว L ตัวมีคำนำหน้า L อัน ดังนั้นคลัง n คำสร้างรายการ n · L รายการ ซึ่งที่ n = 100,000 และ L = 30 คือ 3,000,000 รายการ ยังไหวอยู่ แต่ทุกรายการเป็นสตริง ไม่ใช่ตัวเลข

// นับคำในคลังที่มีคำนำหน้าตามที่ถาม โดยใช้ตารางแฮชของคำนำหน้าทุกอัน
// อินพุต: n q, n คำในคลัง, q คำถาม (คำนำหน้า)
// เอาต์พุต: จำนวนคำในคลังที่เริ่มด้วยคำนำหน้านั้น ทีละบรรทัด
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    unordered_map<string, int> cnt;
    cnt.reserve(1 << 15);
    for (int i = 0; i < n; i++) {
        char buf[64];
        scanf("%s", buf);
        string w = buf;
        // ยัดคำนำหน้าทุกอันของคำนี้ลงตาราง คำยาว L สร้าง L รายการ
        string cur;
        for (char c : w) {
            cur += c;
            cnt[cur]++;
        }
    }
    for (int i = 0; i < q; i++) {
        char buf[64];
        scanf("%s", buf);
        auto it = cnt.find(string(buf));
        printf("%d\n", it == cnt.end() ? 0 : it->second);
    }
    return 0;
}

ทางนี้แพ้ไทรอยู่สามเรื่อง และคุ้มที่จะรู้ว่าแพ้เพราะอะไร

• ค่าใช้จ่ายต่อครั้งไม่คงที่ การแฮชสตริงยาว L ต้องอ่านตัวอักษรครบ L ตัวเพื่อคำนวณค่าแฮชอยู่แล้ว แล้วยังต้องเทียบสตริงเต็มตอนชนช่องเดียวกัน ส่วนไทรเดินทีละตัวอักษร L ก้าวโดยไม่มีการแฮชและไม่มีการเทียบสตริงเลย
• หน่วยความจำโตตามความยาวที่ซ้ำกัน ถ้าคลังมีคำที่ขึ้นต้นเหมือนกันเยอะ ตารางแฮชเก็บคำนำหน้าเดียวกันซ้ำไม่ได้ แต่ก็ต้องเก็บสตริงนั้นไว้หนึ่งชุดอยู่ดี ขณะที่ไทรยุบคำนำหน้าที่ซ้ำกันให้เป็นเส้นทางเดียว ซึ่งเป็นเหตุผลที่มันมีชื่อมาจากคำว่า retrieval ตั้งแต่แรก
• มันตอบได้แค่คำถามที่เตรียมไว้ ตารางแฮชตอบเรื่องการนับคำนำหน้าได้ แต่ตอบไม่ได้เลยว่า "จากจุดนี้เดินต่อได้ด้วยตัวอักษรอะไรบ้าง" ซึ่งเป็นคำถามที่โจทย์เครื่องพิมพ์โบราณ ถามตรง ๆ และเป็นคำถามที่ไทรตอบได้ฟรีเพราะโครงสร้างของมันคือคำตอบ

// ตัวตรวจอิสระ: เทียบคำนำหน้ากับทุกคำในคลังตรง ๆ
// ไม่มีตารางแฮช ไม่มีไทร
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        char buf[64];
        scanf("%s", buf);
        words[i] = buf;
    }
    for (int i = 0; i < q; i++) {
        char buf[64];
        scanf("%s", buf);
        string p = buf;
        int c = 0;
        for (const string& w : words)
            if (w.size() >= p.size() && w.compare(0, p.size(), p) == 0) c++;
        printf("%d\n", c);
    }
    return 0;
}

บทเรียนที่ยกไปใช้ได้คือ ตารางแฮชแลกความง่ายด้วยการทิ้งโครงสร้างของข้อมูลไป มันเก็บทุกคำนำหน้าเป็นก้อนแยกกันที่ไม่รู้จักกัน ส่วนไทรเก็บความสัมพันธ์ระหว่างคำนำหน้าไว้ด้วย พอโจทย์ถามอะไรที่ต้องใช้ความสัมพันธ์นั้น ทางที่ทิ้งมันไปแล้วจะตอบไม่ได้ เจอโจทย์สตริงครั้งหน้าให้ถามก่อนว่า คำถามนี้ต้องรู้แค่ "มีหรือไม่มี" หรือต้องรู้ว่า "เดินต่อไปไหนได้"

เอาไปใช้ที่ไหนในคลังนี้

• เครื่องพิมพ์โบราณ ใช้ไทรเป็นแผนที่ของสถานะเครื่อง ไม่ได้ใช้เพื่อค้นหา ทุกคำสั่งของเครื่องพิมพ์คือหนึ่งก้าวบนไทร

ญาติสนิทของไทรที่ควรรู้ว่ามีอยู่ คือแฮชนำหน้า ซึ่งตอบคำถามคนละแบบ ไทรเก่งเรื่อง "ส่วนหัวร่วมกัน" ส่วนแฮชเก่งเรื่อง "ช่วงตรงกลางสองช่วงเหมือนกันไหม" อ่านได้ที่ แฮชสตริง

สรุปบรรทัดเดียว

ไทรคือการเอาคำทั้งคลังมาซ้อนกันตามส่วนหัว ทำให้คำถามที่เกี่ยวกับส่วนหัวมีราคาเท่ากับความยาวของคำถาม ไม่เกี่ยวกับขนาดของคลัง และเพราะปมหนึ่งปมคือคำนำหน้าหนึ่งอัน มันจึงใช้เป็นแผนที่ของสถานะได้ด้วย ไม่ใช่แค่ที่เก็บคำ