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

Z时代
2024-01-10
分类：综合

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

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

示例

让我们看看以下实现以获得更好的理解 -

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))