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+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習