อัลกอริทึม Kasai สำหรับหา LCP Array

บทนำ

อัลกอริทึม Kasai ใช้หา Longest Common Prefix (LCP) Array จาก Suffix Array หา Suffix Array ก่อน แล้วค่อยใช้ Kasai's Algorithm คำนวณ LCP

ความซับซ้อนของเวลา (Time Complexity)

LCP Array ใช้ O(m log n) ส่วน Kasai's Algorithm ใช้ O(n) สำหรับการค้นหาแพทเทิร์นในข้อความหลัก

อินพุตและเอาต์พุต

Input: Main String: "banana"
Output: Suffix Array : 5 3 1 0 4 2
        Common Prefix Array : 1 3 0 0 2 0

อัลกอริทึม

buildSuffixArray(text)

Input: สตริงหลัก
Output: Suffix Array ที่สร้างจากข้อความ

Begin
    n := ขนาด text
    for i := 0 ถึง n do
        suffArray[i].index := i
        suffArray[i].rank[0] := text[i]
        if (i+1) < n then suffArray[i].rank[1] := text[i+1]
        else suffArray[i].rank[1] := -1
    do
        เรียงลำดับ suffix array
        กำหนด index array
        for k := 4 ถึง (2*n)-1 เพิ่ม k = k*2 do
            currRank := 0, prevRank := suffArray[0].rank[0]
            suffArray[0].rank[0] := currRank
            index[suffArray[0].index] = 0
            for i ทุกตัวของ text do
                if suffArray[i].rank[0] = prevRank AND suffArray[i].rank[1] = suffArray[i-1].rank[1] then
                    prevRank := suffArray[i].rank[0]
                    suffArray[i].rank[0] := currRank
                else
                    prevRank := suffArray[i].rank[0]
                    suffArray[i].rank[0] := currRank + 1
                    currRank := currRank + 1
                    index[suffArray[i].index] := i
            done
            for i ทุกตัวของ text do
                nextIndex := suffArray[i].index + k/2
                if nextIndex < n then suffArray[i].rank[1] := suffArray[index[nextIndex]].rank[0]
                else suffArray[i].rank[1] := -1
            done
            เรียงลำดับ suffArray
        done
        for i ทุกตัวของ text do ใส่ suffArray[i].index เข้า suffVector done
End

kasaiAlgorithm(text, suffVector)

Input: ข้อความหลัก, Suffix Vector
Output: ตำแหน่งที่พบ Longest Common Prefix

Begin
    n := ขนาด suffVector
    กำหนด longPrefix ขนาด n เติม 0, suffInverse ขนาด n เติม 0
    for i ทุกค่าของ suffVector do suffInverse[suffVector[i]] = i done
    k := 0
    for i := 0 ถึง n-1 do
        if suffInverse[i] = n-1 then k := 0, continue
        j := suffVector[suffInverse[i]+1]
        while (i+k) 0 then ลด k 1
    done
    return longPrefix
End

ตัวอย่างโค้ด (C++)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct suffix {
    int index;
    int rank[2];
};

bool compare(suffix s1, suffix s2) {
    if(s1.rank[0] == s2.rank[0]) {
        if(s1.rank[1] < s2.rank[1]) return true;
        else return false;
    } else {
        if(s1.rank[0] < s2.rank[0]) return true;
        else return false;
    }
}

vector<int> buildSuffixArray(string mainString) {
    int n = mainString.size();
    suffix suffixArray[n];
    for (int i = 0; i < n; i++) {
        suffixArray[i].index = i;
        suffixArray[i].rank[0] = mainString[i] - 'a';
        suffixArray[i].rank[1] = ((i+1)0) k--;
    }
    return longPrefix;
}

void showArray(vector<int> vec) {
    for (auto it = vec.begin(); it < vec.end(); it++) cout << *it << " ";
    cout << endl;
}

int main() {
    string mainString = "banana";
    vector<int>suffixArray = buildSuffixArray(mainString);
    cout << "Suffix Array : " << endl;
    showArray(suffixArray);
    vector<int>commonPrefix = kasaiAlgorithm(mainString, suffixArray);
    cout << "\nCommon Prefix Array : " << endl;
    showArray(commonPrefix);
}

ผลลัพธ์

Suffix Array : 5 3 1 0 4 2
Common Prefix Array : 1 3 0 0 2 0