資料結構
網路
關係資料庫管理系統 (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 次瀏覽
