数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用后缀树的模式搜索
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是模式字符串的大小。
458 次浏览
