Самая длинная общая подстрока (используя интуицию для самой длинной общей подпоследовательности)

Question

Я пытался научиться динамическому программированию. И я столкнулся с двумя, казалось бы, похожими проблемами "Самая длинная общая подпоследовательность" и "Самая длинная общая подстрока"

Таким образом, мы предполагаем, что у нас есть 2 строки str1 и str2.

• Для Longest Common Subsequence мы создаем таблицу dp следующим образом:

if str1[i] != str2[j]:
    dp[i][j] = max(dp[i-1][j], sp[i][j-1])
else:
    dp[i][j] = 1 + dp[i-1][j-1]

Следуя той же интуиции, для "LongestОбщая подстрока " можем ли мы сделать следующее:

if str1[i] != str2[j]:
    dp[i][j] = max(dp[i-1][j], sp[i][j-1])
else:
    if str1[i-1] == str2[j-1]:
        dp[i][j] = 1 + dp[i-1][j-1]
    else:
        dp[i][j] = 1 + dp[i-1][j-1]

Проверка if str1[i-1] == str2[j-1] подтверждает, что мы проверяем подстроки, а не подпоследовательность

Answer 1

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

Пусть DP [x] [y] будет максимальной общей подстрокой, учитываяstr1 [0..x] и str2 [0..y].

Учтите, что мы вычисляем DP [a] [b], у нас всегда есть возможность не использовать этот символ = max (DP [a] [b - 1], DP [a - 1] [b]), и если str1 [a] == str2 [b], мы также можем взять ответ DP [a - 1] [b - 1] + 1(+1 существует, потому что мы нашли нового подходящего персонажа)

// This does not depend on s[i] == s[j]
dp[i][j] = max( dp[i][j - 1], dp[i - 1][j] )

if str1[i] == str2[j]:
    dp[i][j] = max( dp[i][j], dp[i - 1][j - 1] + 1 )