Số lượng của tất cả các Hậu tố

Từ văn bản, chúng ta có thể tạo tất cả các hậu tố để tạo cấu trúc cây. Chúng ta biết rằng mọi mẫu hiển thị trong văn bản, phải là tiền tố của một trong các hậu tố có thể có trong văn bản. Bằng cách xây dựng Trie của tất cả các hậu tố, chúng ta có thể tìm thấy bất kỳ chuỗi con nào trong thời gian tuyến tính. Mọi hậu tố đều kết thúc bằng ký hiệu kết thúc chuỗi. Từ mỗi nút nếu có bất kỳ đường dẫn nào, nó sẽ di chuyển về phía trước, nếu không sẽ trả về mẫu đó là không tìm thấy.

Đối với thuật toán này, độ phức tạp thời gian là O (m + k), trong đó m là độ dài của chuỗi và k là tần số của mẫu trong văn bản.

Đầu vào và Đầu ra

Input:
Main String: “ABAAABCDBBABCDDEBCABC”. Pattern “ABC”
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Thuật toán

Trong thuật toán này, chúng ta sẽ sử dụng một nút đặc biệt, được gọi là nút trie. Nó sẽ giữ các chỉ mục của tất cả các hậu tố và địa chỉ các nút trie khác dưới dạng một liên kết.

createTrie (gốc:trieNode, text)

Đầu vào: Nút gốc của loại trieNode.

Đầu ra: Cây hậu tố sử dụng chuỗi chính

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 (mẫu, nút)

Đầu vào: mẫu để tìm và nút, được sử dụng để kiểm tra các cây con hậu tố của nó

Đầu ra - Danh sách chỉ mục nơi mẫu được tìm thấy

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 (mẫu)

Đầu vào - Mẫu sẽ được tìm kiếm

Đầu ra - Danh sách nơi các chỉ mục của văn bản, nơi tìm thấy mẫu

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

Ví dụ

#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;
   }

}

Đầu ra

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