所有后缀的特里
根据文本，我们可以生成所有后缀以构成树结构。我们知道，文本中出现的每个模式都必须是文本中可能的后缀之一的前缀。通过构建所有后缀的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
EndfindPat（模式，节点）
输入：用于查找和结点的模式，用于检入其后缀子树
输出-找到模式的索引列表
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 φ
EndsearchPat（模式）
输入-将搜索的模式
输出- 文本索引，模式所在的列表
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