根据文本,我们可以生成所有后缀以构成树结构。我们知道,文本中出现的每个模式都必须是文本中可能的后缀之一的前缀。通过构建所有后缀的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节点的特殊节点。它将保存所有后缀的索引,而另一个特里节点地址作为链接。
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); //检查索引列表是否为空 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