class sftreeEdge { //边存储起止点(存字符串下标),一个头结点一个尾结点 public: int start_index, end_index; int src_node, dst_node; sftreeEdge(int start, int end, int src, int dst) :start_index(start), end_index(end), src_node(src), dst_node(dst) {} int length() { return end_index - start_index + 1; } }; class sftreeNode { public: int value; int link;//to the longest proper suffix of this node unordered_map<char, sftreeEdge> edges; sftreeNode() :value(-1), link(-1) {} }; class active_point {//活动点 一个三元组 public: int active_node; int active_edge; int active_length; active_point() :active_edge(0), active_length(0), active_node(0) {} }; class suffix_tree { public: active_point a;//活动点 string text; vector<sftreeNode> nodes; suffix_tree(string& s); void show(); int insert_leaf(int, int); int split_edge(sftreeEdge& e, int spos, int pos, int suffix_start); bool suffix_exist(int i);//判断后缀是否已经隐式存在 char active_char();//返回活动点后的第一个字符 int find_substring(const string& substring);//查找子串 vector<int> find_leaves(int start); void find_match(const string& substring); sftreeEdge& active_edge();//返回活动边 sftreeNode& active_node();//返回活动点 void check(); };请给出一个遍历该后缀树的方法
时间: 2024-03-18 17:39:14 浏览: 60
后缀树的遍历可以采用深度优先遍历(DFS)的方法,具体步骤如下:
1. 遍历当前节点的所有子节点的边,对于每条边,先输出其对应的子串;
2. 然后递归遍历该子节点,重复步骤1和2,直到遍历完所有节点。
具体实现可以定义一个递归函数,接受一个节点作为参数,按照上述步骤遍历该节点的子树。代码示例如下:
```
void traverse(sftreeNode& node) {
for (auto& edge : node.edges) {
sftreeEdge& e = edge.second;
// 输出子串
cout << text.substr(e.start_index, e.length()) << endl;
// 递归遍历子节点
traverse(nodes[e.dst_node]);
}
}
// 遍历整个后缀树
void suffix_tree::show() {
traverse(nodes[0]);
}
```
其中 `nodes[0]` 是后缀树的根节点,从根节点开始遍历整个后缀树。此外,为了输出子串,代码中还需要用到原始字符串 `text`。
阅读全文