#23. Eng uzun umumiy qism (LCS)

Lotin alifbosining kichik harflaridan iborat ikkita satr — S1 va S2 beriladi. Siz bu ikki satr uchun eng uzun umumiy qism ketma-ketlik (Longest Common Subsequence) uzunligini topishingiz kerak. Qism ketma-ketlik deb, asl satrdan ba'zi belgilarni o'chirib tashlash (yoki umuman o'chirmaslik) natijasida hosil qilinadigan va qolgan belgilarning asl tartibi buzilmagan yangi satrga aytiladi.

You are given two strings — S1 and S2, consisting of lowercase Latin letters. You need to find the length of the Longest Common Subsequence (LCS) for these two strings. A subsequence is a new string generated from the original string by deleting some characters (or none) without changing the relative order of the remaining characters.

Вам даны две строки — S1 и S2, состоящие из строчных латинских букв. Вам нужно найти длину наибольшей общей подпоследовательности (LCS) для этих двух строк. Подпоследовательность — это новая строка, полученная из исходной путем удаления некоторых символов (или ни одного) без изменения относительного порядка оставшихся символов.