Trie ของทุก Suffix (Trie of all Suffixes)

บทนำ

จากข้อความสามารถสร้าง Suffix ทั้งหมดเป็นโครงสร้างต้นไม้ (Tree) ทุกแพทเทิร์นที่ปรากฏในข้อความ ต้องเป็น Prefix ของ Suffix อย่างน้อยหนึ่งในข้อความ โดยการสร้าง Trie ของ Suffix ทั้งหมด สามารถค้นหา Substring ใดๆ ได้ในเวลาเชิงเส้น

ทุก Suffix จบด้วยสัญลักษณ์สิ้นสุดสตริง จากแต่ละโหนด หากมีเส้นทางต่อไปจะเคลื่อนต่อ มิฉะนั้นคืนค่าไม่พบ

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

O(m + k) โดย m คือความยาวสตริง และ k คือความถี่ของแพทเทิร์นในข้อความ

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

Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern "ABC"
Output: Pattern found at position: 4
        Pattern found at position: 10
        Pattern found at position: 18

อัลกอริทึม

ใช้โหนดพิเศษชื่อ Trie Node เก็บดัชนีของ Suffix ทั้งหมดและที่อยู่ของ Trie Node ถัดไป

createTrie(root: trieNode, text)

Input: โหนดรากประเภท trieNode
Output: ต้นไม้ Suffix จากข้อความหลัก

Begin
    for i := 0 ถึง ความยาวของ text do
        substring จากตำแหน่ง i ถึงสุดท้ายเป็น suffix, ใส่ดัชนี i ใน trie
    done
End

findPat(pattern, node)

Input: แพทเทิร์นที่ต้องการหา, โหนดที่ใช้ตรวจสอบใน subtree
Output: รายการดัชนีที่พบแพทเทิร์น

Begin
    if ขนาด pattern = 0 then return suffIndex ของ node
    if node.suff[pattern[0]] ≠ φ then
        return node.suff[pattern[0]].findPat(substring ตั้งแต่ 1 ถึงสุดของ pattern)
    else return φ
End

searchPat(pattern)

Input: แพทเทิร์นที่จะค้นหา
Output: รายการดัชนีในข้อความที่พบแพทเทิร์น

Begin
    กำหนด res เป็นลิสต์
    res := findPat(pattern)
    if res ≠ φ then
        patLen := ความยาวของ pattern
        for i := 0 ถึงสิ้นสุดของ res list do
            พิมพ์ดัชนีทั้งหมดที่พบแพทเทิร์น
        done
End

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

#include<iostream>
#include<list>
#define MAXCHAR 256
using namespace std;

class trieNode {
    trieNode *suff[MAXCHAR];
    list<int> *suffIndex;
public:
    trieNode() {
        suffIndex = new list<int>();
        for (int i = 0; i < MAXCHAR; i++) suff[i] = NULL;
    }
    void addSuffix(string suffix, int sIndex);
    list<int>* searchPattern(string pat);
};

void trieNode::addSuffix(string suffix, int sIndex) {
    suffIndex->push_back(sIndex);
    if (suffix.size() > 0) {
        char cIndex = suffix[0];
        if (suff[cIndex] == NULL)
            suff[cIndex] = new trieNode();
        suff[cIndex]->addSuffix(suffix.substr(1), sIndex+1);
    }
}

list<int>* trieNode::searchPattern(string pattern) {
    if (pattern.size() == 0) return suffIndex;
    if (suff[pattern[0]] != NULL)
        return (suff[pattern[0]])->searchPattern(pattern.substr(1));
    else return NULL;
}

class trieSuffix {
    trieNode root;
public:
    trieSuffix(string mainString) {
        for (int i = 0; i < mainString.length(); i++)
            root.addSuffix(mainString.substr(i), i);
    }
    void searchPat(string pattern, int *locArray, int *index);
};

void trieSuffix::searchPat(string pattern, int *locArray, int *index) {
    list<int> *res = root.searchPattern(pattern);
    if (res != NULL) {
        list<int>::iterator it;
        int patLen = pattern.length();
        for (it = res->begin(); it != res->end(); it++) {
            (*index)++;
            locArray[(*index)] = *it - patLen;
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    trieSuffix trie(mainString);
    trie.searchPat(pattern, locArray, &index);
    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i] << endl;
    }
}

ผลลัพธ์

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18