Самая длинная общая подстрока и подпоследовательность - PullRequest
Новая
       23

Самая длинная общая подстрока и подпоследовательность

0 голосов
/ 08 сентября 2018

Может ли кто-нибудь однозначно объяснить рекурсивные решения самой длинной общей подпоследовательности и самой длинной общей подстроки и разницы между ними?

1 Ответ

0 голосов
/ 11 сентября 2018

Самая длинная общая подпоследовательность - это классическая проблема, обычно решаемая методом динамического программирования.

Рекурсивное отношение для строк S, T равно: 

/*Characters do not match*/
if(S[i]!=T[j])
   return max(LCS(i+1, j, S, T), LCS(i, j+1, S, T));
else 
   return LCS(i+1, j+1, S, T) + 1;

Здесь i представляет индекс строки S и j строки T. В любом состоянии (i, j) возможны сценарии, либо символы совпадают, либо не совпадают.

  1. Если символы не совпадают, у нас есть два возможных варианта. Либо выберите следующий символ S или выберите следующий символ T и возьмите лучшее из обоих решений.
  2. Если символы совпадают, переходите к следующему символу обеих строк.

Аналогично это можно решить для подстроки

...