ปูพื้นฐาน

แฮชสตริง: เทียบข้อความสองช่วงในเวลาคงที่ โดยรู้ตัวว่ากำลังแลกอะไรอยู่

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

อาการ · คำถามที่ตอบครั้งเดียวก็แพงแล้ว

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

การเทียบหนึ่งครั้งกินเวลาเท่าความยาวช่วง คำถามที่ถามช่วงยาวทั้งเส้นจึงกิน 200,000 ครั้ง และถาม 200,000 ข้อ คือ 40.0 พันล้าน ครั้ง ปัญหาไม่ได้อยู่ที่เราเขียนโค้ดไม่ดี ปัญหาคือเราจ่ายค่าความยาวช่วงซ้ำทุกครั้งที่ถูกถาม ทั้งที่ข้อความไม่เคยเปลี่ยน

บทนี้ว่าด้วยวิธีจ่ายค่านั้นครั้งเดียวตอนต้น แล้วตอบทุกคำถามที่เหลือด้วยการลบเลขครั้งเดียว พร้อมกับส่วนที่คนข้ามบ่อยที่สุดคือมันผิดได้ และผิดบ่อยแค่ไหน

ลองเอง · สองช่วงนี้เหมือนกันไหม

ตอนตอบด้วยตา คุณต้องกวาดดูกี่ตัวอักษรต่อหนึ่งคำถาม แล้วถ้าโจทย์ถามสองแสนครั้งล่ะ

แนวคิด · มองข้อความเป็นตัวเลขฐานหนึ่ง

เลข 4913 ในฐานสิบคือ 4×1000 + 9×100 + 1×10 + 3 เราอ่านมันเป็นตัวเลขก้อนเดียวได้ ทั้งที่มันเป็นลำดับของหลักสี่หลัก ข้อความก็ทำแบบเดียวกันได้ เลือกเลขฐานมาสักตัวเรียกว่า B แล้วมองตัวอักษรแต่ละตัวเป็นหลักหนึ่งหลัก

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

เก็บค่าสะสมไว้ล่วงหน้าแบบเดียวกับผลรวมสะสมในบทก่อน โดย h[i] คือค่าของข้อความตั้งแต่ตัวแรกถึงตัวที่ i

เอาข้อความ abcab มาไล่ให้เห็นจริง โดยให้ a เป็น 1, b เป็น 2, c เป็น 3 และใช้ B = 31 ตารางนี้ยังไม่มีมอดุลัส ตัวเลขจึงตรวจด้วยมือได้

ตัดช่วงกลาง · เลื่อนแล้วลบ

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

ตรวจด้วยมือได้เลยว่าเลข 2016 ที่ได้ คือค่าของ bca จริง ๆ ถ้ากางพหุนามออกมาตรง ๆ

สามอย่างที่ต้องเลือกให้ถูก

หนึ่ง มอดุลัส

ตัวเลขในตารางข้างบนโตเร็วมาก ข้อความยาวสองแสนตัวจะได้เลขที่ยาวเป็นแสนหลัก เก็บใน long long ไม่ได้แน่ ทางแก้คือคิดทุกอย่างในโลกของเศษเหลือจากการหารด้วยจำนวนเฉพาะตัวหนึ่ง

ค่าที่ผมใช้ประจำคือ 2^61 − 1 ซึ่งเป็นจำนวนเฉพาะ และมีคุณสมบัติที่ทำให้การคูณเร็วเป็นพิเศษ คือผลคูณ 122 บิตพับกลับเข้ามาได้ด้วยการเลื่อนบิตกับบวก ไม่ต้องเรียกคำสั่งหารจริงเลย ส่วนมอดุลัสยอดนิยมอย่าง 10^9 + 7 ก็ใช้ได้ แต่เล็กกว่ามาก จนต้องทำสองชุดคู่กัน (double hashing) ถึงจะปลอดภัยพอ ๆ กัน

สอง ฐานต้องสุ่ม

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

สาม ยอมรับว่ามันผิดได้

แฮชยุบข้อความยาว ๆ ให้เหลือเลขก้อนเดียว ข้อความที่ต่างกันจึงมีทางได้เลขเดียวกัน เรียกว่าการชนกัน (collision) เราไม่ได้กำจัดมัน เราแค่ทำให้โอกาสเกิดเล็กจนไม่ต้องสนใจ

คิดคร่าว ๆ ได้ว่าถ้าโปรแกรมเทียบข้อความที่ต่างกันทั้งหมด k คู่ โอกาสที่จะมีสักคู่หนึ่งชนกัน ไม่เกิน k หารด้วยมอดุลัส ที่ k เท่ากับหนึ่งหมื่นล้านคู่ ซึ่งมากกว่าที่โจทย์ไหนจะทำได้จริง ตัวเลขที่ได้คือประมาณ 4.3e-9 หรือราวหนึ่งในสองร้อยล้าน

เขียนเป็นโค้ด

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

// มอดุลัส 2^61 - 1 เป็นจำนวนเฉพาะ และคูณกันแล้ว "พับ" ด้วยการเลื่อนบิตได้ ไม่ต้องหารจริง
const ull MOD = (1ULL << 61) - 1;
static inline ull add(ull a, ull b) { a += b; if (a >= MOD) a -= MOD; return a; }
static inline ull sub(ull a, ull b) { return add(a, MOD - b); }
static inline ull mul(ull a, ull b) {
    __uint128_t c = (__uint128_t)a * b;
    return add((ull)(c & MOD), (ull)(c >> 61));   // ส่วนบน 3 บิต บวกกลับเข้าส่วนล่าง 61 บิต
}

int n;
ull B;
vector<ull> h, pw;

void build(const string& s) {
    n = s.size();
    h.assign(n + 1, 0);
    pw.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        h[i + 1] = add(mul(h[i], B), (ull)(s[i]));
        pw[i + 1] = mul(pw[i], B);
    }
}

// ค่าแฮชของ s[l .. l+len-1] โดย l นับจากศูนย์
ull cut(int l, int len) { return sub(h[l + len], mul(h[l], pw[len])); }

int main() {
    string s;
    int q;
    cin >> s >> q;

    // ฐานสุ่มใหม่ทุกครั้งที่รัน คนแต่งอินพุตมาชนแฮชไม่ได้ถ้าไม่รู้ว่าฐานคืออะไร
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    B = rng() % (MOD - 300) + 256;
    build(s);

    while (q--) {
        int l1, l2, len;
        cin >> l1 >> l2 >> len;                   // ถามว่าสองช่วงนี้เหมือนกันไหม
        cout << (cut(l1, len) == cut(l2, len) ? "YES" : "NO") << '\n';
    }
    return 0;
}

โจทย์ฝึก · ไล่จากง่ายไปยาก

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

ฝึกข้อ 1 ★☆☆☆☆ · นับหน้าต่างที่ไม่ซ้ำกัน

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1;
static inline ull add(ull a, ull b) { a += b; if (a >= MOD) a -= MOD; return a; }
static inline ull sub(ull a, ull b) { return add(a, MOD - b); }
static inline ull mul(ull a, ull b) {
    __uint128_t c = (__uint128_t)a * b;
    return add((ull)(c & MOD), (ull)(c >> 61));
}

int main() {
    int k;
    string s;
    cin >> k >> s;
    int n = s.size();
    if (k > n) { cout << 0 << '\n'; return 0; }

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ull B = rng() % (MOD - 300) + 256;
    vector<ull> h(n + 1, 0), pw(n + 1, 1);
    for (int i = 0; i < n; i++) {
        h[i + 1] = add(mul(h[i], B), (ull)(s[i]));
        pw[i + 1] = mul(pw[i], B);
    }
    auto cut = [&](int l, int len) { return sub(h[l + len], mul(h[l], pw[len])); };

    unordered_set<ull> seen;
    seen.reserve(n * 2);
    for (int i = 0; i + k <= n; i++) seen.insert(cut(i, k));
    cout << seen.size() << '\n';
    return 0;
}

ฝึกข้อ 2 ★★☆☆☆ · ช่วงนี้อ่านกลับแล้วเหมือนเดิมไหม

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1;
static inline ull add(ull a, ull b) { a += b; if (a >= MOD) a -= MOD; return a; }
static inline ull sub(ull a, ull b) { return add(a, MOD - b); }
static inline ull mul(ull a, ull b) {
    __uint128_t c = (__uint128_t)a * b;
    return add((ull)(c & MOD), (ull)(c >> 61));
}

int n;
vector<ull> pw;
static inline ull cut(const vector<ull>& h, int l, int len) {
    return sub(h[l + len], mul(h[l], pw[len]));
}

int main() {
    string s;
    int q;
    cin >> s >> q;
    n = s.size();

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ull B = rng() % (MOD - 300) + 256;

    string r = s;
    reverse(r.begin(), r.end());
    vector<ull> hf(n + 1, 0), hb(n + 1, 0);
    pw.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        hf[i + 1] = add(mul(hf[i], B), (ull)s[i]);
        hb[i + 1] = add(mul(hb[i], B), (ull)r[i]);
        pw[i + 1] = mul(pw[i], B);
    }

    while (q--) {
        int l, rr;
        cin >> l >> rr;
        l--; rr--;                                  // โจทย์นับจาก 1 โค้ดนับจาก 0
        int len = rr - l + 1;
        // ช่วง [l, rr] เมื่ออ่านกลับด้าน ไปอยู่ที่ [n-1-rr, n-1-l] ของสตริงที่กลับแล้ว
        bool ok = cut(hf, l, len) == cut(hb, n - 1 - rr, len);
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

ฝึกข้อ 3 ★★★☆☆ · ท่อนที่ยาวที่สุดที่โผล่ซ้ำ

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1;
static inline ull add(ull a, ull b) { a += b; if (a >= MOD) a -= MOD; return a; }
static inline ull sub(ull a, ull b) { return add(a, MOD - b); }
static inline ull mul(ull a, ull b) {
    __uint128_t c = (__uint128_t)a * b;
    return add((ull)(c & MOD), (ull)(c >> 61));
}

int n;
vector<ull> h, pw;
static inline ull cut(int l, int len) { return sub(h[l + len], mul(h[l], pw[len])); }

// มีสตริงย่อยความยาว len ที่โผล่ซ้ำไหม
bool has(int len) {
    if (len == 0) return true;
    unordered_set<ull> seen;
    seen.reserve(n * 2);
    for (int i = 0; i + len <= n; i++)
        if (!seen.insert(cut(i, len)).second) return true;
    return false;
}

int main() {
    string s;
    cin >> s;
    n = s.size();

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    ull B = rng() % (MOD - 300) + 256;
    h.assign(n + 1, 0);
    pw.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
        h[i + 1] = add(mul(h[i], B), (ull)s[i]);
        pw[i + 1] = mul(pw[i], B);
    }

    // ยาวขึ้นแล้วหายากขึ้นเสมอ คำตอบจึงแบ่งครึ่งค้นได้
    int lo = 0, hi = max(n - 1, 0);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (has(mid)) lo = mid; else hi = mid - 1;
    }
    cout << lo << '\n';
    return 0;
}

ทางที่ไม่มีโอกาสชนเลย · แล้วทำไมยังเลือกแฮชอยู่ดี

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

ท่านั้นคือ Z-algorithm (อ่านว่า "แซดอัลกอริทึม") ซึ่งคำนวณอาเรย์ z[i] ที่แปลว่า คำนำหน้าร่วมที่ยาวที่สุดระหว่างข้อความทั้งเส้น กับข้อความเดียวกันที่ตัดหัวออก i ตัว

ค่านั้นตอบเรื่องการค้นหาได้ตรง ๆ ถ้าอยากรู้ว่า pattern โผล่ที่ไหนใน text ให้เอาสองสตริงมาต่อกันด้วยตัวคั่นที่ไม่มีในทั้งคู่ แล้วดูว่าตำแหน่งไหนใน text มีค่า z ยาวเท่ากับ pattern พอดี ตำแหน่งนั้นคือที่มันโผล่ ไม่มีการเทียบค่าที่อาจเท่ากันโดยบังเอิญเลย เพราะทุกอย่างเทียบด้วยตัวอักษรจริง

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

// Z-algorithm: หาทุกตำแหน่งที่ pattern ปรากฏใน text แบบไม่มีโอกาสชนกันเลย
// อินพุต: บรรทัดแรก pattern บรรทัดสอง text
// เอาต์พุต: จำนวนที่เจอ แล้วตำแหน่งเริ่ม (เริ่มนับจาก 0) เรียงจากน้อยไปมาก
#include <bits/stdc++.h>
using namespace std;

/** z[i] = ความยาวของคำนำหน้าร่วมที่ยาวที่สุด ระหว่าง s กับ s ที่ตัดหัวออก i ตัว */
vector<int> zfunc(const string& s) {
    int n = (int)s.size();
    vector<int> z(n, 0);
    z[0] = n;
    int l = 0, r = 0;                    // ช่วงที่รู้แล้วว่าตรงกับคำนำหน้า
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);   // ใช้ของที่เคยคิดไว้แล้ว
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

int main() {
    string pat, txt;
    if (!(cin >> pat)) return 0;
    if (!(cin >> txt)) txt = "";
    // ต่อกันด้วยตัวคั่นที่ไม่มีในทั้งสองสตริง แล้วช่วงที่ z ยาวเท่า pattern คือที่เจอ
    string joined = pat + '\x01' + txt;
    vector<int> z = zfunc(joined);
    vector<int> at;
    int m = (int)pat.size();
    for (int i = m + 1; i < (int)joined.size(); i++)
        if (z[i] >= m) at.push_back(i - m - 1);
    printf("%d\n", (int)at.size());
    for (size_t i = 0; i < at.size(); i++) printf("%d%c", at[i], i + 1 == at.size() ? '\n' : ' ');
    if (at.empty()) printf("\n");
    return 0;
}

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

int main() {
    string pat, txt;
    if (!(cin >> pat)) return 0;
    if (!(cin >> txt)) txt = "";
    vector<int> at;
    int n = (int)txt.size(), m = (int)pat.size();
    for (int i = 0; i + m <= n; i++) {
        bool ok = true;
        for (int j = 0; j < m && ok; j++) if (txt[i + j] != pat[j]) ok = false;
        if (ok) at.push_back(i);
    }
    printf("%d\n", (int)at.size());
    for (size_t i = 0; i < at.size(); i++) printf("%d%c", at[i], i + 1 == at.size() ? '\n' : ' ');
    if (at.empty()) printf("\n");
    return 0;
}

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

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

มองข้อความเป็นตัวเลขฐาน B แล้วเก็บค่าสะสมไว้ล่วงหน้า การเทียบสองช่วงจะกลายเป็นการลบเลขสองครั้ง โดยมีสามอย่างที่ต้องไม่ลืม มอดุลัสต้องใหญ่ ฐานต้องสุ่ม และช่วงกลับด้านอยู่ที่ n − 1 − r ไม่ใช่ที่เดิม