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

假设我们有一个小写字符串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]
从主要方法中，执行以下操作−
后缀：= a新的列表
n：= s的大小
max_len：= 0
对于范围从0到n – 1的i，做
- 在后缀的末尾插入s [从索引i到n- 1]的子字符串
对列表后缀进行排序
对于后缀中的每个项目a和后缀[from index 1 to end的子字符串，做
- 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））