Как восстановить строки в "edit_distance_problem"?

Question

Предположим, что вы дали дп таблицу для строки X = "AGGGCT" и строка Y = "AGGCA"

м = длина X + 1

п = длина Y + 1

  0 1 2 3 4 5 
      1 0 1 2 3 4 
      2 1 0 1 2 3 
dp[m][n] = 3 2 1 0 1 2 
      4 3 2 1 1 2 
      5 4 3 2 1 2 
      6 5 4 3 2 2 

и вы хотите восстановить три строки следующим образом

string row1 = "AGGGCT" ; 
string row2 = "||| | " ; 
string row3 = "AGG-CA" ; 

Как recontruct струны ROW1, ROW2 и row3, если это возможно после кода в C/C++/Java.

Answer 1

Я думаю, что эта страница может быть хорошей отправной точкой:

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Java

Вы должны сделать несколько модификаций, но основная идея должна быть хранить в «мин», который дело выбранной выше для (i, j), а перед возвратом вы можете пройти через матрицу назад, начиная с расстояния [str1.length()] [str2.length()] шаг за шагом. Если на этапах расстояния одинаковы, вы показываете |, если они отличаются друг от друга, но ступенчатая диагональ, то это был шаг изменения, иначе, если вертикально/горизонтально удалить/добавить. Вы можете сохранить эту «обратную» информацию в строке, а затем отобразить ее в обратном порядке.