Как я могу эффективно найти длину самой длинной общей подстроки между двумя строками? ⇐ Python

[Anonymous]

У меня есть две строки: s1 и s2, и мне нужно найти длину самой длинной подстроки, которая встречается в обеих строках. Подстрока должна быть непрерывной как в s1, так и в s2.
Например:

• Если s1 = "abcde" и s2 = "cdefg", самой длинной общей подстрокой будет "cde", длина которой равна 3.
• Если s1 = "abcdef" и s2 = "ghijkl", общей подстроки нет, поэтому результат должен быть 0 .

Я ищу эффективное решение, которое может обрабатывать большие строки, длиной до 1000 символов.
Я попробовал использовать метод грубой силы, проверив все подстроки одной строки и проверив, существуют ли они в другой строке. Однако этот подход слишком медленный для входных данных большого размера. Я ожидал эффективного решения с использованием динамического программирования, но не знаю, как его правильно настроить.
Вот что я пробовал:
def longestCommonSubstring(s1, s2):
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
max_len = 0
for i in range(1, len(s1) + 1):
for j in range(1, len(s2) + 1):
if s1[i-1] == s2[j-1]:
dp[j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[j])
return max_len

Это отлично работает для небольших тестовых случаев, но мне интересно, является ли это наиболее эффективным решением или есть более эффективные подходы. Есть ли способ улучшить его или это разумный подход для больших входных данных?


Подробнее здесь: https://stackoverflow.com/questions/791 ... strings-ef