Chương trình tìm độ dài của chuỗi con lặp lại dài nhất trong một chuỗi bằng Python

Giả sử chúng ta có một chuỗi chữ thường s, chúng ta phải tìm độ dài của chuỗi con dài nhất xảy ra ít nhất hai lần trong s. Nếu chúng tôi không thể tìm thấy chuỗi như vậy, hãy trả về 0.

Vì vậy, nếu đầu vào giống như s ="Abdgoalputabdtypeabd", thì đầu ra sẽ là 3, vì chuỗi con dài nhất xuất hiện nhiều lần là "Abd".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm lcs (). Điều này sẽ mất s1, s2
• n:=kích thước tối thiểu của s1 và kích thước của s2
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • nếu s1 [i] không giống với s2 [i], thì
    • trả về chuỗi con của s1 [từ chỉ mục 0 đến i-1]
• trả về chuỗi con của s1 [từ chỉ mục 0 đến n - 1]
• Từ phương pháp chính, hãy thực hiện như sau -
• hậu tố:=một danh sách mới
• n:=kích thước của s
• max_len:=0
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • chèn (chuỗi con của s [từ chỉ mục i đến n - 1]) vào cuối các hậu tố
• sắp xếp các hậu tố trong danh sách
• đối với mỗi mục a từ các hậu tố và b từ chuỗi con của các hậu tố [từ chỉ mục 1 đến cuối], hãy thực hiện
  • rtr:=lcs (a, b)
  • nếu kích thước của rtr> max_len, thì
    • max_len:=kích thước của rtr
• trả về max_len

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

"abdgoalputabdtypeabd"

Đầu ra

3