Tìm chuỗi con dài nhất là tiền tố, hậu tố và cũng có mặt bên trong chuỗi bằng Python

Giả sử chúng ta có một chuỗi cho trước, chúng ta phải tìm chuỗi con lớn nhất là tiền tố, hậu tố và chuỗi con của chuỗi đã cho đó. Nếu không có chuỗi con như vậy, thì trả về -1.

Vì vậy, nếu đầu vào giống như "languagepythonlanguageinterestinglanguage", thì đầu ra sẽ là "ngôn ngữ"

Để 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 get_lps (). Điều này sẽ lấy chuỗi

• n:=kích thước của chuỗi

• long_pref_suff:=một mảng có kích thước n và điền bằng 0

• size:=0, long_pref_suff [0]:=0, i:=1

• trong khi i

  • nếu chuỗi [i] giống với chuỗi [size] thì

    • size:=size + 1

    • long_pref_suff [i]:=size

    • i:=i + 1

  • nếu không,

    • nếu kích thước không bằng 0 thì

      • size:=long_pref_suff [size - 1]

    • nếu không,

      • long_pref_suff [i]:=0

      • i:=i + 1

• trả về long_pref_suff

• Từ phương thức chính, thực hiện như sau -

• long_pref_suff:=get_lps (chuỗi)

• n:=kích thước của chuỗi

• nếu long_pref_suff [n - 1] giống 0 thì

  • trả về -1

• đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện

  • nếu long_pref_suff [i] giống long_pref_suff [n - 1] thì

    • trả về chuỗi con của chuỗi [từ chỉ mục 0 đến long_pref_suff [i]]

• nếu long_pref_suff [long_pref_suff [n - 1] - 1] bằng 0 thì

  • trả về -1

• nếu không,

  • trả về chuỗi con của chuỗi [từ chỉ mục 0 đến long_pref_suff [long_pref_suff [n - 1] - 1]]

Ví dụ

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

def get_lps(string):
   n = len(string)
   long_pref_suff = [0 for i in range(n)]
   size = 0
   long_pref_suff[0] = 0
   i = 1
   while (i < n):
      if (string[i] == string[size]):
         size += 1
         long_pref_suff[i] = size
         i += 1
      else:
         if (size != 0):
            size = long_pref_suff[size - 1]
         else:
            long_pref_suff[i] = 0
            i += 1
   return long_pref_suff
def get_longest_substr(string):
   long_pref_suff = get_lps(string)
   n = len(string)
   if (long_pref_suff[n - 1] == 0):
      return -1
   for i in range(0,n - 1):
      if (long_pref_suff[i] == long_pref_suff[n - 1]):
         return string[0:long_pref_suff[i]]
      if (long_pref_suff[long_pref_suff[n - 1] - 1] == 0):
         return -1
      else:
         return string[0:long_pref_suff[long_pref_suff[n - 1] - 1]]

string = "languagepythonlanguageinterestinglanguage"
print(get_longest_substr(string))

Đầu vào

"languagepythonlanguageinterestinglanguage"

Đầu ra

language