모든 접미사 시도

텍스트에서 모든 접미사를 생성하여 트리 구조를 만들 수 있습니다. 우리는 텍스트에 있는 모든 패턴이 텍스트에서 가능한 접미사 중 하나의 접두사여야 한다는 것을 알고 있습니다. 모든 접미사의 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