Поиск самой длинной общей последовательности

-3

Я, прочитав статью, нахожу самую длинную общую между двумя строками.Поиск самой длинной общей последовательности

Я узнал об алгоритме, который кода в следующем:

for(int i=0;i<=n;i++) 
    for(int j=0;j<=m;j++){ 

     if(i==0 || j==0) dd[i][j]=0; 
     else if(a[i-1]==b[j-1]) 
      dd[i][j] = 1 + dd[i-1][j-1]; 
     else{ 
      dd[i][j] = Math.max(dd[i-1][j], dd[i][j-1]); 
     } 
    }

я оставил это понять, но я не мог понять, как это работает, то есть то, что является доказательством работы правильно. Почему эта вещь работа, пожалуйста, помогите мне разобраться в алгоритме

источник

2014-12-21 QWE

Пытались ли вы чтение [статьи Википедии] (http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution)? – amit

Пусть

str1 = "bcd" 
str2 = "dabc"

здесь n=3 и m=4

The outer loop is for str1 and inner loop is for str2

первой итерации используется для инициализации массива.

Вот первый взгляд dd массива:

0, 0, 0, 0, 0 
0, 0, 0, 0, 0 
0, 0, 0, 0, 0 
0, 0, 0, 0, 0

Во 2 итерации внешнего цикла, он сравнивает весь str2 с 1-го символа строки str1, то есть "dabc" with 'b'

теперь, когда 'b' сравнивается с "dabc", мы видим, что на 4-й итерации будет совпадение, поэтому значение массива будет изменено относительно corne r значение текущей позиции. Текущая позиция: [1][3]. В углу ([0][2]) значение 0, текущее значение будет 1:

0, 0, 0, 0, 0 
0, 0, 0, 1, 0 
0, 0, 0, 0, 0 
0, 0, 0, 0, 0

В конце итерации массив будет выглядеть следующим образом:

0, 0, 0, 0, 0 
0, 0, 0, 1, 1 
0, 0, 0, 0, 0 
0, 0, 0, 0, 0

значение позиции [1][4] изменилось, потому что, если характер str2 не совпадает с текущим символом str1, тогда значение текущей позиции будет максимальным между верхней и левой позицией текущего положения. Здесь max - 1.

Теперь проверьте себя, если максимальное совпадение str1="b" будет 1. Это мы рассчитываем максимальное соответствие для каждой записи str1 на каждой итерации.

В 3-й итерации внешнего цикла, он сравнивает весь str2 снова с 2-го характера str1, что "dabc" with 'c'

теперь в 5 итерации будет матч, так что значение массива будет изменено относительно значения угла текущей позиции. Текущая позиция: [2][4].В углу ([1][3]) значение 1, текущее значение будет 2:

0, 0, 0, 0, 0 
0, 0, 0, 1, 1 
0, 0, 0, 1, 2 
0, 0, 0, 0, 0

Теперь проверьте себя, если str1="bc" максимальное совпадение будет 2. То есть мы расчетливый максимальное соответствие для каждой записи str1 в каждой итерации.

В конце итерации массив будет выглядеть следующим образом:

0, 0, 0, 0, 0 
0, 0, 0, 1, 1 
0, 0, 0, 1, 2 
0, 0, 0, 0, 0

В 4-й итерации внешнего цикла, он сравнивает весь str2 снова с 3-го характера str1, то есть "dabc" with 'd'

теперь на 2-й итерации будет соответствовать, поэтому значение массива будет изменено относительно значения угла текущего положения. Текущая позиция: [3][1]. В углу ([2][0]) значение 0, текущее значение будет 1:

0, 0, 0, 0, 0 
0, 0, 0, 1, 0 
0, 0, 0, 0, 2 
0, 1, 0, 0, 0

не далее соответствия не будет происходить.

В конце итерации массив будет выглядеть следующим образом:

0, 0, 0, 0, 0 
0, 0, 0, 1, 1 
0, 0, 0, 1, 2 
0, 1, 1, 1, 2

Так ЛВП из этих двух струн dd[3][4] = 2.

Надеюсь, вы это понимаете. Вы также можете получить помощь от here

Примечание: Здесь я описал только о соответствии ситуации. Если один символ str2 не совпадает с текущим символом str1, то значение текущей позиции будет максимальным между верхним и левым положениями текущего положения. Попробуйте сами, вы поймете, почему мы делаем это :)

источник

2014-12-21 17:52:09

Есть много ресурсов, которые можно найти, если вы Google ..

Это с 1-го link [Word Aligned]. Существует хорошее объяснение с анимацией

источник

2014-12-21 18:13:41 aerokite

Поиск самой длинной общей последовательности

ответ

Смежные вопросы