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

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

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

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

• 定义一个函数 lcs()。它将接收 s1 和 s2 作为参数。
• n := s1 和 s2 大小的最小值
• 对于 i 从 0 到 n - 1 的范围，执行以下操作：
  • 如果 s1[i] 与 s2[i] 不相同，则
    • 返回 s1 的子字符串（从索引 0 到 i-1）
• 返回 s1 的子字符串（从索引 0 到 n - 1）
• 从主方法中执行以下操作：
• suffixes := 一个新的列表
• n := s 的大小
• max_len := 0
• 对于 i 从 0 到 n - 1 的范围，执行以下操作：
  • 将 (s 的子字符串（从索引 i 到 n - 1））插入到 suffixes 的末尾
• 对列表 suffixes 进行排序
• 对于 suffixes 中的每个项目 a 和 suffixes 的子字符串（从索引 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))

输入

"abdgoalputabdtypeabd"

输出

3

Arnab Chakraborty

更新于: 2021年10月19日

2K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习