这篇简单的谈谈后缀树原理及实现。
如前缀树原理一般，后缀trie树是将字符串的每个后缀使用trie树的算法来构造。例如banana的所有后缀：
0: banana
1: anana
2: nana
3: ana
4: na
5: a
按字典序排列后：
5: a
3: ana
1: anana
0: banana
4: na
2: nana
形成一个树形结构。
代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// banana中不重复的字符有：a b n
/*
* a b n
* n $ a a
* a n n $
* n $ a a
* a n $
* $ a
$*/
#define SIZE 27
#define Index(c) ((c) - 'a')
#define rep(i, a, b) for(i = a; i < b; i++)
typedef struct BaseNode {
struct BaseNode*next[SIZE];
char c;
int num;
} suffix_tree, *strie;
void initialize(strie* root)
{
int i;
*root = (strie)malloc(sizeof(suffix_tree));
(*root)->c = 0;
(*root)->num = -1;
rep(i, 0, SIZE) (*root)->next[i] = NULL;
}
void insert(strie*root, const char*str, int k)
{
suffix_tree*node = *root, *tail;
int i, j;
for (i = 0; str[i] != '\0'; i++)
{
if (node->next[Index(str[i])] == NULL)
{
tail = (strie)malloc(sizeof(suffix_tree));
tail->c = str[i];
tail->num = -1;
rep(j, 0, SIZE) tail->next[j] = NULL;
node->next[Index(str[i])] = tail;
}
node = node->next[Index(str[i])];
}
tail = (strie)malloc(sizeof(suffix_tree));
tail->c = '$';
tail->num = k;
rep(i, 0, SIZE) tail->next[i] = NULL;
node->next[SIZE - 1] = tail;
}
void show(suffix_tree*root)
{
if (root)
{
int i;
rep(i, 0, SIZE) show(root->next[i]);
printf("%c\n", root->c);
if (root->num > -1)
{
printf("%d\n", root->num);
}
}
}
void destory(strie*root)
{
if (*root)
{
int i;
rep(i, 0, SIZE) destory(&(*root)->next[i]);
free(*root);
*root = NULL;
}
}
int main()
{
suffix_tree*root; initialize(&root); char str[] = "banana", *p = str;
int i = 0;
while(*p)
{
insert(&root, p, i);
p++;
i++;
}
show(root);
destory(&root);
return 0;
}
时间复杂度分析：算法中对于建立一串长m的字符串，需要一个外层的m次循环 + 一个内层m次循环 + 一些常数，于是建立一颗后缀字典树所需的时间为O(m2)，27的循环在这里可看作常数；
空间复杂度分析：一个字符的字符串长度为1，需要消耗的1个该字符 + 1个根节点 + 1个\$字符的空间，两个字符的字符串长度为2，需要消耗3个字符空间+ 1个根节点 + 2个\$空间...以此类推，发现总是含有1个根节点和m个\$字符，\$的个数等于字符串长度m，而存储的源字符串后缀所需的空间有如下规律：
$$ \begin{aligned} O(s_1) &= 1 \\ O(s_2) &= 1+2 \\ O(s_3) &= 1+2+3 \\ \cdot \cdot \cdot \\ O(s_m) &= 1+2+ \cdot \cdot \cdot + m \end{aligned} $$
设以长为m的字符串s建立后缀树T，于是有：
$$ O(T) = O(\frac{(1 + m)m}{2} + 1 + m) = O(m^2) $$
由于上面算法对于无重复的字符串来说空间复杂度比较大，所以使用路径压缩以节省空间，这样的树就称为后缀树，也可以通过下标来存储，如图：
p.s.写压缩路径的后缀树时，脑子犯傻了...错了，改天再把正确的补上。。。
路径压缩版后缀树：
#include <iostream>
using namespace std;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define trans(c) (c - 'a')
#define SIZE 26
#define MAX (100010 << 2)
struct BaseNode {
int len;
const char*s;
int pos[MAX];
BaseNode*next[SIZE];
BaseNode()
{
len = 0;
rep(i, 0, MAX) pos[i] = 0;
rep(i, 0, SIZE) next[i] = nullptr;
}
BaseNode(const char*s, int p)
{
this->s = s, this->len = p;
rep(i, 0, MAX) pos[i] = 0;
rep(i, 0, SIZE) next[i] = nullptr;
}
};
class SuffixTree {
private:
BaseNode*root;
/**/
void add(const char*s, int p);
void print(BaseNode*r);
void destory(BaseNode*&r);
public:
SuffixTree()
{
root = nullptr;
}
void insert(const char*s);
void insert(string s)
{
insert(s.c_str());
}
void remove(const char*s)
{ }
void visual()
{
print(root);
}
bool match(const char*s);
bool match(string s)
{
match(s.c_str());
}
~SuffixTree()
{
destory(root);
}
};
void SuffixTree::add(const char*s, int p)
{
int i = 0; while (s[i]) i++;
if (!root->next[p]) root->next[p] = new BaseNode(s, i);
root->next[p]->pos[i] = i;
}
void SuffixTree::insert(const char*s)
{
root = new BaseNode();
while (*s)
{
add(s, trans(*s));
s++;
}
}
bool SuffixTree::match(const char*s)
{
const char* ps = root->next[trans(*s)]->s;
while (*s) if (*ps++ != *s++) return false;
return true;
}
void SuffixTree::print(BaseNode*r)
{
if (r)
{
rep(i, 0, SIZE)
if (r->next[i])
{
cout << i << ':' << endl;
rep(j, 0, r->next[i]->len + 1)
if (r->next[i]->pos[j])
{
rep(k, 0, r->next[i]->pos[j])
cout << r->next[i]->s[k];
cout << '$' << endl;
}
}
}
}
void SuffixTree::destory(BaseNode*&r)
{
if (r)
{
rep(i, 0, SIZE) destory(r->next[i]);
delete r;
}
}
int main()
{
SuffixTree st;
st.insert("banana");
st.visual();
if (st.match("na")) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
上面的后缀树都是对于一个字符串的处理方法，而广义后缀树将算法推广到了不同的字符串上，但我还没写过，改天补上。。。
参考：https://en.wikipedia.org/wiki/Suffix_tree