30.4 ค้นหาข้อความด้วย prefix function

หน้า 13.5 หาคำในประโยคด้วยการวางคำไว้ทุกตำแหน่งแล้วเทียบทีละตัวอักษร ข้อความยาว n คำยาว m ใช้เวลาไม่เกิน O(nm) ข้อมูลทั่วไปเทียบไม่กี่ตัวก็เจอตัวที่ไม่ตรงแล้ว จึงเร็วมาก แต่ข้อมูลบางแบบทำให้ต้องเทียบเกือบครบทุกครั้ง หน้านี้สอน prefix function ซึ่งเป็นแกนของวิธี KMP (Knuth Morris Pratt) ค้นหาคำได้ใน O(n + m) เสมอ และยังบอกโครงสร้างการซ้ำของข้อความได้อีกด้วย

ข้อมูลที่ทำให้วิธีไล่ช้า

ข้อความเป็น a ล้านตัว คำเป็น a 999 ตัวตามด้วย b ทุกตำแหน่งที่วางคำลงไป ตัวอักษร 999 ตัวแรกตรงหมด มาไม่ตรงที่ตัวสุดท้าย จึงเทียบราวพันครั้งต่อตำแหน่ง รวมราว 10⁹ ครั้ง ถ้าคำยาวขึ้นเป็นหมื่น ก็เป็นราว 10¹⁰ ครั้ง

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

ส่วนต้นที่เป็นส่วนท้ายด้วย

ส่วนต้นของข้อความ s ที่ไม่ใช่ทั้งข้อความ และบังเอิญเป็นส่วนท้ายของ s ด้วย เรียกว่า border เช่น abacaba มี border สองตัวคือ a กับ aba ส่วน abcd ไม่มีเลย

prefix function ของข้อความ s คืออาเรย์ border ที่ border[i] เท่ากับความยาวของ border ที่ยาวที่สุดของส่วนต้นยาว i + 1 ตัว คือ s[0] ถึง s[i] ถ้าไม่มี border เลยก็เป็น 0 ค่าของ abababaa ทุกตำแหน่งอยู่ในผลของโปรแกรมในหัวข้อถัดไป

คำนวณใน O(n)

สมมติรู้ border[i - 1] แล้ว ให้ j เป็นค่านั้น แปลว่า j ตัวแรกของ s ตรงกับ j ตัวที่จบที่ตำแหน่ง i - 1 อยากต่อ border นี้ให้ยาวขึ้นอีกตัวด้วย s[i]

• ถ้า s[i] == s[j] ต่อได้ทันที border[i] = j + 1
• ถ้าไม่ตรง ต้องลอง border ที่สั้นกว่าของส่วนที่จบที่ i - 1 border ตัวถัดไปที่สั้นกว่า j ก็คือ border ของส่วนต้นยาว j ตัวนั้นเอง เพราะมันเป็นทั้งส่วนต้นและส่วนท้ายของ j ตัวนั้น ซึ่งคือ border[j - 1] ค่าที่คำนวณไว้แล้ว ถอย j ไปแบบนี้จนต่อได้หรือ j เป็น 0

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    vector<int> border(n, 0);
    for (int i = 1; i < n; i++) {
        int j = border[i - 1]; // (1)!
        while (j > 0 && s[i] != s[j]) {
            cout << "i=" << i << " '" << s[i] << "' != '" << s[j] << "', fall back from " << j << " to " << border[j - 1] << '\n';
            j = border[j - 1]; // (2)!
        }
        if (s[i] == s[j]) {
            j++; // (3)!
        }
        border[i] = j;
    }
    for (int i = 0; i < n; i++) {
        cout << s.substr(0, i + 1) << " " << border[i] << '\n';
    }
    return 0;
}

1. เริ่มจาก border ที่ยาวที่สุดของตัวก่อนหน้า ซึ่งเป็นตัวที่ดีที่สุดที่อาจต่อได้
2. ต่อไม่ได้ ถอยไป border ที่ยาวรองลงมา ต้องเป็น while เพราะอาจต้องถอยหลายครั้ง
3. ตัวอักษรตรงกัน border ยาวขึ้นหนึ่ง ถ้า j ถอยจนเป็น 0 แล้วยังไม่ตรงอีก border ก็เป็น 0

abababaa

i=7 'a' != 'b', fall back from 5 to 3
i=7 'a' != 'b', fall back from 3 to 1
i=7 'a' != 'b', fall back from 1 to 0
a 0
ab 0
aba 1
abab 2
ababa 3
ababab 4
abababa 5
abababaa 1

ตัวที่ 2 คือ b ไม่ตรงกับตัวแรก จึงได้ 0 ตั้งแต่ตัวที่ 3 ถึงตัวที่ 7 ต่อได้ทุกครั้ง border ยาวขึ้นทีละหนึ่งจนเป็น 5 คือ ababa ซึ่งเป็นทั้งส่วนต้นและส่วนท้ายของ abababa ตัวสุดท้าย a ต่อกับ ababa ไม่ได้ จึงถอยไป border ยาว 3 คือ aba ต่อไม่ได้อีก ถอยไป 1 คือ a ต่อไม่ได้อีก ถอยไป 0 แล้วเทียบกับตัวแรกจึงต่อได้ ได้ 1 ซึ่งคือ a ตัวเดียวที่เป็นทั้งตัวแรกและตัวสุดท้าย

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

ค่าสุดท้ายของอาเรย์บอก border ที่ยาวที่สุดของทั้งข้อความ ซึ่งเกี่ยวกับการที่ข้อความซ้ำตัวเองเป็นลาย ลองคิดต่อในแบบฝึกหัด

ค้นหาคำ

ต่อคำ ตัวคั่น และข้อความเข้าด้วยกันเป็น word + "#" + text แล้วหา prefix function ของข้อความที่ต่อแล้ว ตำแหน่งที่ border ยาวเท่ากับ m พอดี แปลว่าส่วนท้ายยาว m ตัวที่จบตรงนั้นตรงกับส่วนต้นยาว m ตัว ซึ่งก็คือคำ เท่ากับเจอคำในข้อความ ตัวคั่น # ต้องไม่อยู่ในคำและข้อความ border จึงข้ามตัวคั่นไม่ได้ และยาวเกิน m ไม่ได้

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string &s)
{
    int n = s.size();
    vector<int> border(n, 0);
    for (int i = 1; i < n; i++) {
        int j = border[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = border[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        border[i] = j;
    }
    return border;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string text, word;
    cin >> text >> word;
    int m = word.size();
    string joined = word + "#" + text; // (1)!
    vector<int> border = prefix_function(joined);
    int count = 0;
    for (int i = m + 1; i < (int)joined.size(); i++) {
        if (border[i] == m) {
            cout << "found at " << i - 2 * m << '\n'; // (2)!
            count++;
        }
    }
    cout << "count = " << count << '\n';
    return 0;
}

1. ตัวอักษรของ text ช่องที่ k อยู่ช่อง m + 1 + k ของ joined
2. คำจบที่ช่อง i ของ joined คือช่อง i - m - 1 ของข้อความ จึงเริ่มที่ช่อง i - m - 1 - (m - 1) = i - 2m ของข้อความ

abaababaabaab
abaab

found at 0
found at 5
found at 8
count = 3

คำที่ตำแหน่ง 5 กับ 8 ซ้อนกันสองตัวอักษร นับได้ทั้งคู่แบบนับซ้อนในหน้า 13.5 ทั้งหมดเป็น O(n + m) ไม่ว่าข้อมูลจะเป็นแบบไหน อัลกอริทึม KMP แบบดั้งเดิมไม่ได้ต่อข้อความ แต่เดินบนข้อความโดยใช้ prefix function ของคำ ผลเหมือนกัน แบบต่อข้อความเขียนสั้นกว่าและจำง่ายกว่า อีกเครื่องมือที่ทำงานคล้ายกันคือ Z-function ซึ่งก็ค้นหาคำได้ใน O(n + m) เลือกจำแบบเดียวก็พอ

เร็วขึ้นแค่ไหน

เทียบสามวิธี คือวิธีไล่แบบหน้า 13.5 เขียนด้วย string การเรียก text.find(word, pos + 1) วนหาทุกตำแหน่งแบบหน้า 15.4 และ prefix function ทุกวิธีนับจำนวนตำแหน่งที่เจอเท่านั้น ข้อความยาวล้านตัวอักษร วัดบนเครื่องเดียวกับหน้า 18.2 แบบ -O2 รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

กับข้อความสุ่ม ทั้งสามวิธีเร็วเท่ากัน เพราะวิธีไล่เจอตัวที่ไม่ตรงตั้งแต่ตัวแรกๆ string::find ของ g++ เทียบได้เร็วกว่าลูปที่เราเขียนเองราวสิบเท่า แต่ยังโตตามความยาวของคำ คำยาวขึ้นสิบเท่า เวลาก็ยาวขึ้นราวสิบเท่า ส่วน prefix function แทบไม่เปลี่ยนเลย ถ้าโจทย์ไม่ได้บอกว่าข้อมูลสุ่ม และขอบเขตทำให้ n × m เกินราว 10⁹ อย่าพึ่ง find

ลองทำให้พัง

แบบที่ 1 ลืมตัวคั่น

ในโปรแกรม find-all ต่อเป็น word + text เฉยๆ แล้วปรับสูตรตำแหน่งให้ตรงกับที่ข้อความเริ่มช่อง m แทน m + 1 ค้น aa ใน aaa ซึ่งโปรแกรม find-all ตอบว่าเจอที่ 0 กับ 1 รวม 2 ตำแหน่ง

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string &s)
{
    int n = s.size();
    vector<int> border(n, 0);
    for (int i = 1; i < n; i++) {
        int j = border[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = border[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        border[i] = j;
    }
    return border;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string text, word;
    cin >> text >> word;
    int m = word.size();
    string joined = word + text;
    vector<int> border = prefix_function(joined);
    int count = 0;
    for (int i = m; i < (int)joined.size(); i++) {
        if (border[i] == m) {
            cout << "found at " << i - 2 * m + 1 << '\n';
            count++;
        }
    }
    cout << "count = " << count << '\n';
    return 0;
}

aaa
aa

found at -1
count = 1

ข้อความที่ต่อแล้วคือ aaaaa prefix function เป็น 0 1 2 3 4 ที่ช่อง 2 border ยาว 2 พอดี แต่ aa ตัวนั้นใช้ a ตัวท้ายของคำกับ a ตัวแรกของข้อความ จึงได้ตำแหน่ง -1 ที่ไม่มีอยู่จริง ส่วนสองช่องหลังได้ border ยาว 3 กับ 4 เกิน m ไปแล้ว ตำแหน่งที่เจอจริงทั้งสองจึงหายไป ตัวคั่นทำหน้าที่กั้นไม่ให้ border ยาวเกินคำ และไม่ให้ข้ามจากคำมาที่ข้อความ

แบบที่ 2 ถอยแค่ครั้งเดียว

ในโปรแกรม border-table เปลี่ยน while เป็น if เพราะคิดว่าถอยครั้งเดียวก็พอ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    vector<int> border(n, 0);
    for (int i = 1; i < n; i++) {
        int j = border[i - 1];
        if (j > 0 && s[i] != s[j]) {
            j = border[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        border[i] = j;
    }
    for (int i = 0; i < n; i++) {
        cout << s.substr(0, i + 1) << " " << border[i] << '\n';
    }
    return 0;
}

abababaa

a 0
ab 0
aba 1
abab 2
ababa 3
ababab 4
abababa 5
abababaa 3

ทุกบรรทัดตรงกับของจริง ยกเว้นบรรทัดสุดท้ายที่ได้ 3 แทน 1 ถอยจาก 5 ไป 3 แล้ว s[3] คือ b ยังไม่ตรงกับ a แต่ไม่ได้ถอยต่อ และไม่ได้บวกหนึ่ง j จึงค้างที่ 3 ซึ่งผิด เพราะ aba ไม่ใช่ส่วนท้ายของ abababaa ที่ลงท้ายด้วย baa ข้อความส่วนใหญ่ถอยครั้งเดียวก็พอ ความผิดนี้จึงหลุดชุดทดสอบเล็กๆ ได้ง่าย ทดสอบ prefix function ด้วยข้อความที่ต้องถอยหลายครั้งแบบ abababaa เสมอ

สรุป

• border คือส่วนต้นที่เป็นส่วนท้ายด้วย border[i] คือ border ที่ยาวที่สุดของ i + 1 ตัวแรก
• คำนวณจาก j = border[i - 1] ถ้าไม่ตรงให้ถอย j = border[j - 1] ด้วย while ตรงแล้วบวกหนึ่ง รวมทั้งข้อความเป็น O(n)
• หาคำด้วย prefix function ของ word + "#" + text ตำแหน่งที่ได้ m คือเจอคำ เริ่มที่ช่อง i - 2m ของข้อความ ทั้งหมด O(n + m)
• ตัวคั่นต้องไม่อยู่ในคำและข้อความ ลืมตัวคั่นแล้วจะได้ตำแหน่งปลอมและหายบางตำแหน่ง
• วิธีไล่และ string::find เร็วกับข้อมูลทั่วไป แต่ช้าเป็น O(nm) กับข้อมูลที่ตั้งใจดัก
• IOI Syllabus 2023 จัด KMP ไว้ในกลุ่มที่ไม่ออกข้อสอบ หัวข้อนี้เป็นความรู้เสริมสำหรับคนที่ชอบสตริง

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด