Suffix Array (อาร์เรย์ Sufffix)

บทนำ

จากสตริงที่กำหนด สามารถหา Suffix ทั้งหมดได้ หลังจากเรียงลำดับ Suffix ตามลำดับเล็กซิโคกราฟิก (Lexicographical Order) จะได้ Suffix Array สามารถสร้างได้จาก Suffix Tree ด้วยการท่อง DFS

Suffix Array ช่วยค้นหา Suffix ได้ในเวลาเชิงเส้น และค้นหา Substring ได้ด้วยกระบวนการแบบ Binary Search

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

O(m log n)

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

Input: Main String: "BANANA", Pattern: "NAN"
Output: Pattern found at position: 2

อัลกอริทึม

fillSuffixArray(text, suffArray)

Input: สตริงหลัก
Output: อาร์เรย์ของ Suffix

Begin
    n := ความยาวของ text
    กำหนด suffix array ชื่อ allSuffix ขนาด n
    for i := 0 ถึง n-1 do
        allSuffix[i].index := i
        allSuffix[i].suff := substring ของ text จาก i ถึงสุดท้าย
    done
    เรียงลำดับ allSuffix array
    เก็บดัชนีของ allSuffix ที่เรียงแล้วใน suffArray
End

suffixArraySearch(text, pattern, suffArray)

Input: สตริงหลัก, แพทเทิร์น, suffix array
Output: ตำแหน่งที่พบแพทเทิร์น

Begin
    patLen := ขนาดของ pattern
    strLen := ขนาดของ text
    left := 0, right := strLen - 1
    while left <= right do
        mid := left + (right - left)/2
        tempStr := substring ของ text จาก suffArray[mid] ถึงสุดท้าย
        result := เปรียบเทียบ tempStr และ pattern จนถึงความยาว pattern
        if result = 0 then พิมพ์ตำแหน่ง
        if result < 0 then right := mid - 1
        else left := mid + 1
    done
End

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

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

struct suffix {
    int index;
    string suff;
};

int strCompare(string st1, string st2, int n) {
    int i = 0;
    while(n--) {
        if(st1[i] != st2[i]) return st1[i] - st2[i];
        i++;
    }
    return 0;
}

bool comp(suffix suff1, suffix suff2) {
    if(suff1.suff < suff2.suff) return true;
    return false;
}

void fillSuffixArray(string mainString, int suffArr[]) {
    int n = mainString.size();
    suffix allSuffix[n];
    for(int i = 0; i

ผลลัพธ์
Pattern found at position: 2