Python Найти наибольшую общую подстроку двух строк
Задача о самой длинной общей подстроке состоит в следующем: даны две строки, нужно найти самую длинную общую подстроку между ними. Подстрока — это непрерывная последовательность символов в строке. Для решения этой задачи можно использовать динамическое программирование.
Пример
def longest_common_substring(s1, s2):
m = len(s1)
n = len(s2)
# Создать двумерный массив для хранения длины самой длинной общей подстроки
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # Записать длину самой длинной общей подстроки
end_pos = 0 # Записать конечную позицию самой длинной общей подстроки
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_length = dp[i][j]
end_pos = i
else:
dp[i][j] = 0
# Вернуть самую длинную общую подстроку
return s1[end_pos - max_length:end_pos]
#
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("Самая длинная общая подстрока:", result)
m = len(s1)
n = len(s2)
# Создать двумерный массив для хранения длины самой длинной общей подстроки
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # Записать длину самой длинной общей подстроки
end_pos = 0 # Записать конечную позицию самой длинной общей подстроки
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_length:
max_length = dp[i][j]
end_pos = i
else:
dp[i][j] = 0
# Вернуть самую длинную общую подстроку
return s1[end_pos - max_length:end_pos]
#
s1 = "abcdef"
s2 = "zbcdf"
result = longest_common_substring(s1, s2)
print("Самая длинная общая подстрока:", result)
Пояснение кода:
dp— это двумерный массив,dp[i][j]представляет строкуs1первыеiсимволов и строкуs2первыеjсимволов длины самой длинной общей подстроки.- Мы перебираем каждый символ двух строк, если
s1[i-1]иs2[j-1]равны, тоdp[i][j]значение ... равноdp[i-1][j-1] + 1, иначеdp[i][j]равен 0. max_lengthиспользуется для записи длины самой длинной общей подстроки,end_posиспользуется для записи конечной позиции самой длинной общей подстроки.- Наконец, мы используем
s1[end_pos - max_length:end_pos]чтобы получить самую длинную общую подстроку.
Результат вывода:
最长公共子串是: bcdДругие расширения
Python3 Примеры