0
我正在處理後綴樹。據我所知，我已經正確運行了Ukkonen的算法，可以從任意數量的字符串中構建通用後綴樹。我現在試圖實現一個find_longest_common_substring()方法來做到這一點。爲了這個工作，我知道我需要在樹中的所有字符串之間找到最深的共享邊（字符深度而不是邊），並且我一直在掙扎幾天來獲得遍歷權。通用後綴樹遍歷查找最長公共子串
現在我在C++中有以下內容。我會盡量提供所有代碼，但對於上下文，我將每個節點的邊緣保留在一個名爲outgoing_edges的unordered_map中，並且每個邊都有一個包含識別添加的字符串的整數的整數的向量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類似的問題，但方法似乎有足夠的差異，我不太確定它是如何適用於此。
我主要是爲了好玩和學習，所以我不一定需要工作代碼來替換上面的僞代碼，或者只是對我困惑的地方的任何解釋都一樣。