用 Python 编写程序，查找字符串中最长重复子字符串的长度

pythonserver side programmingprogramming更新于 2026/1/23 12:28:17

假设我们有一个小写字符串 s，我们必须找到 s 中出现至少两次的最长子字符串的长度。如果我们找不到这样的字符串，则返回 0。

因此，如果输入为 s = "abdgoalputabdtypeabd"，则输出将为 3，因为出现多次的最长子字符串是 "abd"。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 lcs() 。这将需要 s1、s2
n := s1 的大小和 s2 的大小中的最小值
对于范围在 0 到 n - 1 内的 i，执行
- 如果 s1[i] 与 s2[i] 不同，则
  - 返回 s1 的子字符串[从索引 0 到 i-1]
返回 s1 的子字符串[从索引 0 到 n - 1]
从主方法中，执行以下操作 −
后缀 := 一个新列表
n := s 的大小
max_len := 0
对于范围在 0 到 n - 1 内的 i，执行
- 在后缀末尾插入(s 的子字符串[从索引 i 到 n - 1])
对列表后缀进行排序
对于后缀中的每个项目 a 和后缀子字符串[从索引 1 到末尾] 中的 b，执行
- rtr := lcs(a, b)
- 如果 rtr 的大小 > max_len，则
  - max_len := rtr 的大小
返回 max_len

示例

让我们看看下面的实现以便更好地理解 −

def lcs(s1, s2):
   n = min(len(s1), len(s2))

   for i in range(n):
      if s1[i] != s2[i]:
         return s1[:i]
   return s1[:n]

def solve(s):
   suffixes = []
   n = len(s)
   max_len = 0

   for i in range(n):
      suffixes.append(s[i:n])

   suffixes.sort()

   for a, b in zip(suffixes, suffixes[1:]):
      rtr = lcs(a, b)

      if len(rtr) > max_len:
         max_len = len(rtr)

   return max_len

s = "abdgoalputabdtypeabd"
print(solve(s))