使用后缀树的模式搜索

---

Trie树 − Trie树是一种基于树的数据结构，用于存储和检索动态字符串集。

压缩Trie树 − 压缩Trie树是Trie树的一种变体，用于存储和搜索动态字符串集。通过共享公共前缀来最小化内存使用。

在压缩Trie树中，只有单个子节点的节点与其父节点合并，将公共前缀压缩到单个边中。

后缀树 − 后缀树是一种用于字符串处理的数据结构，用于存储和搜索给定字符串的所有后缀。它以树状结构的形式表示字符串的所有可能后缀，其中每条边代表一个子字符串，每个节点代表字符串中的一个位置。根节点代表空字符串，叶子节点代表字符串的所有唯一后缀。

为给定字符串创建后缀树

• 生成给定字符串的所有后缀。

• 例如，单词“world”−

Suffixes of “world\0” are:
world\0
orld\0
rld\0
ld\0
d\0
\0

• 将每个后缀作为单独的单词，创建一个压缩Trie树。

问题陈述

给定一个输入字符串“str”和一个模式字符串“ptr”。使用后缀树判断模式字符串“ptr”是否出现在输入字符串“str”中，以及它们出现的索引。

示例 1

Input: str = “aabcdaaabcdbabc”
ptr = “abc”
Output: 1, 7, 12

解释

模式“abc”出现在输入字符串的索引 1、7 和 12。

示例 2

Input: str = “minimization”
ptr = “ma”
Output: False

解释

模式“ma”未在输入字符串中找到。

解决方案方法

为了在后缀树中搜索ptr，我们首先查看模式的第一个字符，并将其与根节点的子节点进行匹配。如果匹配，则我们在子节点上递归搜索。但是，如果在任何时候模式与子节点不匹配，则模式不存在于字符串中。

伪代码

class Node
   children[256]: Node array
   ind: List of integers

   constructor()
      ind <- create new empty list of integers
      for i from 0 to 255
         children[i] <- NULL

   function insertSuffix(suffix: string, index: integer)
      ind.push_back(index)
      if suffix.length() > 0
         cIndex <- suffix.at(0)
         if children[cIndex] is NULL
            children[cIndex] <- create new Node
         children[cIndex].insertSuffix(suffix.substr(1), index + 1)

   function search(pat: string): List of integers
      if pat.length() is 0
         return ind
      if children[pat.at(0)] is not NULL
         return children[pat.at(0)].search(pat.substr(1))
      else
         return NULL


class SuffixTree
   root: Node

   constructor(txt: string)
      root <- create new Node
      for i from 0 to txt.length() - 1
         root.insertSuffix(txt.substr(i), i)

   function search(ptr: string)
      ans <- root.search(ptr)
      if ans is NULL
         print "Pattern not found"
      else
         for each i in ans
            print "Pattern found at position " + (i - ptr.length())

示例：C++ 实现

以下代码使用后缀树搜索字符串中的模式。

#include <bits/stdc++.h>
using namespace std;

// Defining node of the Suffix tree
class Node{
private:
   Node *children[256];
   list<int> *ind;
public:
   Node(){
      ind = new list<int>;
      for (int i = 0; i < 256; i++) {
         children[i] = NULL;
      }
   }
   // Inserting new suffix to the tree
   void insertSuffix(string suffix, int index){
      ind->push_back(index);
      if (suffix.length() > 0){
         char cIndex = suffix.at(0);
         if (children[cIndex] == NULL)
            children[cIndex] = new Node();
         children[cIndex]->insertSuffix(suffix.substr(1), index + 1);
      }
   }
   // Pattern Searching in subtree
   list<int> *search(string pat){
      if (pat.length() == 0)
         return ind;
      if (children[pat.at(0)] != NULL)
         return (children[pat.at(0)])->search(pat.substr(1));
      else
         return NULL;
   }
};

// Defination of Suffix Tree
class SuffixTree {
private:
   Node root;
public:
   SuffixTree(string txt){
      for (int i = 0; i < txt.length(); i++)
         root.insertSuffix(txt.substr(i), i);
   }
   // Function for searching a pattern in the tree
   void search(string ptr){
      list<int> *ans = root.search(ptr);
      if (ans == NULL)
         cout << "Pattern not found" << endl;
      else {
         list<int>::iterator i;
         int ptrLength = ptr.length();
         for (i = ans->begin(); i != ans->end(); i++){
            cout << "Pattern found at position " << *i - ptrLength << endl;
         }
      }
   }
};
int main(){
   string str = "aabcdaaabcdbabc";
   string ptr = "abcx";
   SuffixTree Tree(str);
   cout << "Searching for " << ptr << endl;
   Tree.search(ptr);
   return 0;
}

输出

Searching for abcx
Pattern not found

时间复杂度 −

后缀树构建 − O(N^2)，其中N是输入字符串的长度，这是最坏情况下的时间复杂度。

模式搜索 − O(M)，其中M是模式的长度。

空间复杂度 −

后缀树构建 − O(N^2)，其中N是输入字符串的长度，这是最坏情况下的空间复杂度。

模式搜索 − O(1)

结论

总之，后缀树是一种强大的数据结构，可以有效地存储和操作字符串。它允许进行各种与字符串相关的操作，包括子字符串搜索、模式匹配以及前缀/后缀查询。使用后缀树在字符串中进行模式搜索是一种有效的方法。提供的解决方案以O(M)的时间复杂度和O(1)的空间复杂度解决了问题，其中M是模式字符串的大小。