Chương trình tìm ra sự giống nhau giữa một chuỗi và các hậu tố của nó trong python

Giả sử, chúng ta được cung cấp một chuỗi 'input_str'. Nếu chúng ta xác định tất cả các hậu tố từ input_str; ví dụ:nếu chuỗi là 'abcd', các hậu tố là 'abc', 'bcd', 'cd', 'd'. Bây giờ, chúng ta kiểm tra sự giống nhau giữa input_str và tất cả các hậu tố bằng độ dài của tiền tố chung dài nhất trong input_str và một hậu tố. Tổng các điểm tương đồng giữa input_str và tất cả các hậu tố phải được trả về.

Vì vậy, nếu đầu vào là input_str ='tpotp', thì đầu ra sẽ là 7

Tất cả các hậu tố từ chuỗi 'tpotp' là 'tpotp', 'potp', 'otp', 'tp' và 'p'.

Nếu chúng tôi kiểm tra sự giống nhau của tất cả các hậu tố với input_str, thì chúng tôi nhận được -

'tpotp' similarity 5
'potp' similarity 0
'otp' similarity 0
'tp' similarity 2
'p' similarity 0

Sum of similarities = 5 + 0 + 0 + 2 + 0 = 7.

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

• return_list:=một danh sách mới chứa kích thước của input_str
• i:=1
• p:=0
• q:=0
• r:=0
• while i
• nếu q
• nếu return_list [i-q]> =q + p-i, thì
  • r:=q + p - i
  • p:=0
  • q:=0
• nếu không,
  • chèn return_list [i-q] vào cuối return_list
  • i:=i + 1
  • r:=0

def solve(input_str):
   return_list = [len(input_str)]
   i = 1
   p, q = 0,0
   r = 0
   while i < len(input_str):
      if q < i < (q+p):
         if return_list[i-q] >= q+p-i:
            r = q + p - i
            p, q = 0, 0
         else:
            return_list.append(return_list[i-q])
            i += 1
            r = 0
      else:
         while i + r < len(input_str) and input_str[r] == input_str[i+r]:
            r += 1
         return_list.append(r)
         p,q = r,i
         i += 1
         r = 0
      return sum(return_list)

print(solve('tpotp'))

'tpotp'

5