ลองคำต่อท้ายทั้งหมด

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

สำหรับอัลกอริทึมนี้ ความซับซ้อนของเวลาคือ 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

อัลกอริทึม

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

createTrie (ราก:trieNode, ข้อความ)

ป้อนข้อมูล: โหนดรูทของประเภท trieNode

ผลลัพธ์: ต้นไม้ต่อท้ายโดยใช้สตริงหลัก

Begin
   for i := 0 to length of text, do
      substring from ith position to end as suffix, and add in index i in tire.
   done
End

findPat(รูปแบบ, โหนด)

ป้อนข้อมูล: รูปแบบเพื่อค้นหาและโหนด ซึ่งใช้ตรวจสอบในทรีย่อยต่อท้าย

ผลลัพธ์ − รายการดัชนีที่พบรูปแบบ

Begin
   if pattern size is 0, then
      return suffIndex of node
   if node.suff[patten[0]] ≠φ, then
      return node.suff[pattern[0]].findPat(substring from 1 to end o pattern)
   else
      return φ
End

searchPat(รูปแบบ)

ป้อนข้อมูล - รูปแบบที่จะค้นหา

ผลลัพธ์ − รายการที่ดัชนีของข้อความที่พบรูปแบบ

Begin
   define res as list.
   res := findPat(pattern)

   if res ≠φ, then
      patLen := length of pattern
      for i := 0 to end of res list, do
         print all indexes where pattern was found
      done
End

ตัวอย่าง

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

class trieNode {      //node to hold all suffixes
   private:
      trieNode *suff[MAXCHAR];
      list<int> *suffIndex;
   public:
      trieNode() {
         suffIndex = new list<int>;
         for (int i = 0; i < MAXCHAR; i++)
            suff[i] = NULL;       //no child initially
      }

      void addSuffix(string suffix, int sIndex);
      list<int>* searchPattern(string pat);
};

void trieNode::addSuffix(string suffix, int sIndex) {
   suffIndex->push_back(sIndex);        //store index initially

   if (suffix.size() > 0) {
      char cIndex = suffix[0];
      if (suff[cIndex] == NULL)        //if no sub tree present for this character
         suff[cIndex] = new trieNode();     //create new node
      suff[cIndex]->addSuffix(suffix.substr(1), sIndex+1);      //for next suffix
   }
}

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));    //follow to next node
   else
      return NULL;       //when no node are there to jump
}

class trieSuffix {      //trie for all suffixes
   trieNode root;
   public:
      trieSuffix(string mainString) {       //add suffixes and make trie
         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);
   // Check if the list of indexes is empty or not
   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