глубины первого поиск

Question

У меня есть суффикс дерево, каждый узел этого дерева является структурой

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

мне нужно сделать для каждой глубину узла и получить все строки, которые я могу достичь, но я не умеют делать. Это мой ДФС функционировать

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> > 

где ИНТ узел моих дерева и вектора строк, которые я могу достичь

прямо сейчас он работает

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); 
    } 
}