Pythonの文字列で最も長く繰り返される部分文字列の長さを見つけるプログラム

小文字の文字列sがあるとすると、sで少なくとも2回出現する最長の部分文字列の長さを見つける必要があります。そのような文字列が見つからない場合は、0を返します。

したがって、入力がs ="abdgoalputabdtypeabd"の場合、複数回出現する最長のサブストリングは "abd"であるため、出力は3になります。

これを解決するには、次の手順に従います-

• 関数lcs（）を定義します。これにはs1、s2が必要です
• n：=s1の最小サイズとs2のサイズ
• 0からn-1の範囲のiの場合、do
  • s1[i]がs2[i]と同じでない場合、
    • s1の部分文字列を返す[インデックス0からi-1へ]
• s1の部分文字列を返す[インデックス0からn-1まで]
• メインの方法から、次の手順を実行します-
• サフィックス：=新しいリスト
• n：=sのサイズ
• max_len：=0
• 0からn-1の範囲のiの場合、do
  • 接尾辞の最後に（s [インデックスiからn-1]の部分文字列）を挿入します
• リストのサフィックスを並べ替える
• 各項目について、接尾辞からのaと接尾辞のサブストリングからのb[インデックス1から最後まで]を実行します
  • rtr：=lcs（a、b）
  • rtrのサイズ>max_lenの場合、
    • max_len：=rtrのサイズ
• return 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