Python最长公共子串算法实例

最长公共子串是指在两个字符串中，找到最长的相同子串。这是一个常见的字符串处理问题，也是算法设计中的重要问题之一。Python作为一种强大的编程语言，可以使用多种算法来解决这个问题。本文将介绍Python中常用的最长公共子串算法，并给出实例代码。

一、暴力枚举法

暴力枚举法是最朴素的算法，它的基本思路是对两个字符串中的每个子串进行比较，找到最长的相同子串。具体实现方法如下：

```python

def longest_common_substring(s1, s2):

m, n = len(s1), len(s2)

result = ''

for i in range(m):

for j in range(n):

k = 0

while i + k < m and j + k < n and s1[i + k] == s2[j + k]:

k += 1

if len(result) < k:

result = s1[i:i+k]

return result

```

这个算法的时间复杂度是O(m*n*(m+n))，在处理大量数据时会非常慢，因此不适合实际应用。

二、动态规划法

动态规划法是一种高效的算法，它的基本思路是将问题分解为子问题，并使用已知的子问题解来构建更大的问题解。对于最长公共子串问题，动态规划法的实现方法如下：

```python

def longest_common_substring(s1, s2):

m, n = len(s1), len(s2)

max_len = 0

end = 0

dp = [[0] * (n + 1) for _ in range(m + 1)]

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_len:

max_len = dp[i][j]

end = i

else:

dp[i][j] = 0

return s1[end - max_len:end]

```

这个算法的时间复杂度是O(m*n)，效率比暴力枚举法高很多。同时，该算法还可以通过记录起始位置来返回所有的最长公共子串。

三、后缀数组法

后缀数组法是一种高效的字符串匹配算法，它的基本思路是将一个字符串的所有后缀排序，然后比较相邻后缀的公共前缀，最长公共前缀即为最长公共子串。对于最长公共子串问题，后缀数组法的实现方法如下：

```python

def longest_common_substring(s1, s2):

s = s1 + '#' + s2 + '$'

n = len(s)

sa = sorted(range(n), key=lambda i: s[i:])

lcp = [0] * (n - 1)

for i in range(1, n):

x, y = sa[i - 1], sa[i]

while s[x:x+lcp[i-1]] == s[y:y+lcp[i-1]]:

lcp[i-1] += 1

max_len, end = max((lcp[i], sa[i]) for i in range(n - 1))

return s[end - max_len:end]

```

这个算法的时间复杂度是O(n*logn)，效率比动态规划法高，但实现比较复杂。

四、总结

本文介绍了Python中常用的最长公共子串算法，分别为暴力枚举法、动态规划法和后缀数组法。其中，暴力枚举法虽然简单，但时间复杂度过高，不适合实际应用；动态规划法是一种高效的算法，时间复杂度为O(m*n)，可以处理大量数据；后缀数组法是一种更高效的算法，时间复杂度为O(n*logn)，但实现比较复杂。根据实际需求，可以选择适合的算法来解决最长公共子串问题。