#define sigma 26
typedef struct suffix_tree{
struct suffix_tree * subtree[sigma];
char * lable;
int size;
} suffix_tree;
suffix_tree *
create_empty_suffix_tree(char * string) {
int w, i, j;
suffix_tree * stree = 0;
if (string < 0) return 0;
stree = (suffix_tree *) malloc(sizeof(suffix_tree));
memset(stree, sizeof(suffix_tree), 0);
if (string > 0) {
stree->lable = (char*)malloc(w + 1);
strcpy(stree->lable, string);
stree->size = w;
}
return stree;
}
void
split_insert(suffix_tree * stree, int k, char * str) {
int w, i, j;
suffix_tree * new = 0;
int w = strlen(str);
new = (suffix_tree*) malloc(sizeof(suffix_tree));
new->lable = (char*)malloc(stree->size -k + 2);
strcpy(new->lable, stree->lable + k);
new->size = stree->size - k + 1;
new->subtree = stree->subtree;
stree->subtree = {0,};
stree->subtree[k] = new;
for (i = k; i < stree->size && stree->lable[i]; ++i)
stree->lable[i-1] = stree->lable[i];
stree->lable[i] = 0;
stree->size = k - 1;
new = (suffix_tree*)malloc(sizeof(suffix_tree);
new->substree = {0,};
new->lable = (char*) malloc(w - k + 2);
strcpy(new->lable, str + k);
new-size = w - k + 1;
stree->subtree[str[k]] = new;
}
void
construct_suffix_tree(suffix_tree * stree, char * text) {
int w, m, i, j;
suffix_tree * curstree = 0;
w = strlen(text);
for (i = w -1; i >=0; --i) {
m = w - i;
j = i;
curstree = stree;
while (curstree->subtree[text[j]]) {
k = 0;
while ((k < curstree->subtree[text[j]]->size)
&& (curstree->subtree[text[j]]->lable[k] == text[j+k])
++k;
if (k + 1 < curstree->subtree[text[j]]->size)
split_insert(curstree->subtree[text[j]], k, text[j]);
else {
j += k;
curstree = curstree->subtree[text[j]];
}
}
if (j < m && !curstree->subtree[text[j]])
curstree->subtree[text[j]] = create_empty_suffix_tree(text[j]);
}
}
st.rar_后缀树
版权申诉
73 浏览量
2022-09-21
07:25:46
上传
评论
收藏 720B RAR 举报
邓凌佳
- 粉丝: 65
- 资源: 1万+
最新资源
- pta题库答案c语言之排序4统计工龄.zip
- pta题库答案c语言之树结构7堆中的路径.zip
- pta题库答案c语言之树结构3TreeTraversalsAgain.zip
- pta题库答案c语言之树结构2ListLeaves.zip
- pta题库答案c语言之树结构1树的同构.zip
- 基于C++实现民航飞行与地图简易管理系统可执行程序+说明+详细注释.zip
- pta题库答案c语言之复杂度1最大子列和问题.zip
- 三维装箱问题(Three-Dimensional Bin Packing Problem,3D-BPP)是一个经典的组合优化问题
- 以下是一些关于Linux线程同步的基本概念和方法.txt
- 以下是一个简化的示例,它使用pygame库来模拟烟花动画的框架.txt
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈