48 lines
1.5 KiB
Python
48 lines
1.5 KiB
Python
# -*- coding: utf-8 -*-
|
||
# @Time : 2024/4/13 13:23
|
||
# @Author : len
|
||
# @File : 最长公共子串.py
|
||
# @Software: PyCharm
|
||
# @Comment :
|
||
|
||
def longest_common_substring(strs):
|
||
if not strs:
|
||
return ""
|
||
|
||
# 定义一个函数来寻找两个字符串的最长公共子串
|
||
def lcs(s1, s2):
|
||
n, m = len(s1), len(s2)
|
||
# 初始化动态规划表
|
||
dp = [[0] * (m + 1) for _ in range(n + 1)]
|
||
longest, x_longest = 0, 0 # 存储最长公共子串的长度和结束位置
|
||
for i in range(1, n + 1):
|
||
for j in range(1, m + 1):
|
||
if s1[i - 1] == s2[j - 1]: # 当字符相同
|
||
dp[i][j] = dp[i - 1][j - 1] + 1
|
||
if dp[i][j] > longest: # 更新最长公共子串的信息
|
||
longest = dp[i][j]
|
||
x_longest = i
|
||
else:
|
||
dp[i][j] = 0 # 字符不同，公共子串长度重置为0
|
||
return s1[x_longest - longest: x_longest] # 返回最长公共子串
|
||
|
||
# 从列表中的第一个字符串开始，逐步与后续字符串比较
|
||
common_sub = strs[0]
|
||
for s in strs[1:]:
|
||
common_sub = lcs(common_sub, s)
|
||
if not common_sub: # 如果公共子串长度为0，提前终止
|
||
break
|
||
|
||
return common_sub
|
||
|
||
# 输入的字符串列表
|
||
strings = [
|
||
"a1b2c3d4e5",
|
||
"a2b2c3d4e4",
|
||
"a3b3c3d4e6",
|
||
"a5b2c3d4e5"
|
||
]
|
||
|
||
# 调用函数，找出最长的公共子串
|
||
result = longest_common_substring(strings)
|
||
print(result) |