私はサフィックスツリーを扱っています。私が知る限り、任意の数の文字列から一般化されたサフィックスツリーを構築するためにUkkonenのアルゴリズムを正しく実行しています。私は今、正確にそれを行う方法find_longest_common_substring()を実装しようとしています。これがうまくいくためには、ツリー内のすべての文字列の間で、最も深い共有エッジ（エッジではなく文字の点での深さ）を見つける必要があることを理解しています。そして、トラバースを正しく行うために数日間苦労しています。最も一般的な部分文字列を見つける一般的なサフィックスツリートラバーサル
今、私はC++で次のことをしています。私はあなたのすべてのコードを忘れませんが、文脈のために、私はoutgoing_edgesと呼ばれるunordered_mapの各ノードのエッジを保ちます、そして、各エッジは、追加された文字列を識別する整数を含むint recorded_stringsのベクトルを持っています。エッジのchildフィールドは、それが行くノードであり、lおよびrは、それぞれ左端および右端のインデックスを識別する。最後に、current_string_numberはツリー内の文字列の現在の数です。
SuffixTree::Edge * SuffixTree::find_deepest_shared_edge(SuffixTree::Node * start, int current_length, int &longest) {
Edge * deepest_shared_edge = new Edge;
auto it = start->outgoing_edges.begin();
while (it != start->outgoing_edges.end()) {
if (it->second->recorded_strings.size() == current_string_number + 1) {
int edge_length = it->second->r - it->second->l + 1;
int path_length = current_length + edge_length;
find_deepest_shared_edge(it->second->child, path_length, longest);
if (path_length > longest) {
longest = path_length;
deepest_shared_edge = it->second;
}
}
it++;
}
return deepest_shared_edge;
}
デバッグしようと、私が言うことができる最善のように、トラバースはほとんどが正常に動作し、正しくパスの長さを記録し、最長設定します。しかし、私がかなり理解していない理由のために、最も内側の条件では、deepest_shared_edgeが誤ったエッジに更新されることがあります。私は多分、it->secondがどのように再帰を通して更新されるのかよく分かりません。しかし、私はこれを修正する方法についてはあまりよく分かりません。
私はthisと似た質問をしていますが、アプローチが十分に異なるように見えますが、ここでどのように適用するかはわかりません。
私は主に楽しく学んでいるので、上記の擬似コードを置き換えるための作業コードや、混乱している場所の説明だけを必要とするわけではありません。