深度优先搜索

Question

我有一个后缀树，这棵树的每个节点是一个结构

struct state { 
int len, link; 
map<char,int> next; }; 
state[100000] st; 

我需要为每个节点DFS和得到，我可以接触到所有的字符串，但我不知道如何制作。 这是我的DFS功能

void getNext(int node){ 
    for(map<char,int>::iterator it = st[node].next.begin();it != st[node].next.end();it++){ 
     getNext(it->second); 
} 
} 

这将是完美的，如果我能像

map<int,vector<string> > 

其中int是我的树和矢量串的节点，我可以达到

现在它的工作原理

void createSuffices(int node){//, map<int, vector<string> > &suffices) { 
if (suffices[sz - 1].size() == 0 && (node == sz - 1)) { 
    // node is a leaf 
    // add a vector for this node containing just 
    // one element: the empty string 
    //suffices[node] = new vector<string> 
    //suffices.add(node, new vector<string>({""})); 
    vector<string> r; 
    r.push_back(string()); 
    suffices[node] = r; 
} else { 
    // node is not a leaf 
    // create the vector that will be built up 
    vector<string> v; 
    // loop over each child 
    for(map<char,int>::iterator it = st[node].next.begin();it != st[node].next.end();it++){ 
     createSuffices(it->second); 
     vector<string> t = suffices[it->second]; 
     for(int i = 0; i < t.size(); i ++){ 
      v.push_back(string(1,it->first) + t[i]); 
     } 
    } 
    suffices[node] = v; 
} 
} 

Answer 1

您可以通过map<int, vector<string>>来获得她与你的深度第一次搜索。当递归调用从某个节点n返回时，您知道该节点的所有足够的准备就绪。我的C++技能是太有限了，所以我会在伪代码写：

void createSuffices(int node, map<int, vector<string>> suffices) { 
    if (st[node].next.empty()) { 
     // node is a leaf 
     // add a vector for this node containing just 
     // one element: the empty string 
     suffices.add(node, new vector<string>({""})); 
    } else { 
     // node is not a leaf 
     // create the vector that will be built up 
     vector<string> v; 
     // loop over each child 
     foreach pair<char, int> p in st[node].next { 
      // handle the child 
      createSuffices(p.second, suffices); 

      // prepend the character to all suffices of the child 
      foreach string suffix in suffices(p.second) { 
       v.add(concatenate(p.first, suffix)); 
      }     
     } 
     // add the created vector to the suffix map 
     suffices.add(node, v); 
    } 
}