数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究所有后缀的 Trie 树
从文本中，我们可以生成所有后缀以构建树形结构。我们知道文本中出现的每个模式都必须是文本中某个可能后缀的前缀。通过构建所有后缀的 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
算法
在此算法中，我们将使用一个特殊的节点，称为 Trie 节点。它将保存所有后缀的索引以及另一个 Trie 节点的地址作为链接。
createTrie(root: trieNode, text)
输入：一个 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(pattern, node)
输入：要查找的模式和节点，用于在其后缀子树中进行检查
输出 − 找到模式的索引列表
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(pattern)
输入 − 将要搜索的模式
输出 − 文本中找到模式的索引列表
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
更新于: 2020年6月15日
427 次查看
广告