โปรแกรมค้นหาความคล้ายคลึงกันระหว่างสตริงและส่วนต่อท้ายใน python

สมมติว่าเราได้รับสตริง 'input_str' ถ้าเรากำหนดคำต่อท้ายทั้งหมดจาก input_str; ตัวอย่างเช่น ถ้าสตริงคือ 'abcd' ส่วนต่อท้ายคือ 'abc', 'bcd', 'cd', 'd' ตอนนี้ เราตรวจสอบความคล้ายคลึงกันระหว่าง input_str และส่วนต่อท้ายทั้งหมดด้วยความยาวของคำนำหน้าที่ยาวที่สุดใน input_str และส่วนต่อท้าย ต้องส่งคืนผลรวมของความคล้ายคลึงระหว่าง input_str และส่วนต่อท้ายทั้งหมด

ดังนั้น หากอินพุตเป็นเหมือน input_str ='tpotp' ผลลัพธ์จะเป็น 7

คำต่อท้ายทั้งหมดจากสตริง 'tpotp' คือ 'tpotp', 'potp', 'otp', 'tp' และ 'p'

หากเราตรวจสอบความคล้ายคลึงของคำต่อท้ายทั้งหมดด้วย input_str เราจะได้ -

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

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• return_list :=รายการใหม่ที่มีขนาดของ input_str
• ผม :=1
• p :=0
• q :=0
• r :=0
• ในขณะที่ฉัน <ขนาดของ input_str ทำ
  • ถ้า q
  • ถ้า return_list[i-q]>=q+p-i แล้ว
    • r :=q + p - i
    • p :=0
    • q :=0
  • มิฉะนั้น
    • แทรก return_list[i-q] ที่ส่วนท้ายของ return_list
    • ผม :=ผม + 1
    • r :=0
• มิฉะนั้น
  • ในขณะที่ (i + r <ขนาดของ input_str) และ (input_str[r] เท่ากับ input_str[i+r]) ทำ
    • r :=r + 1
  • ใส่ r ที่ส่วนท้ายของ return_list
  • p :=r
  • q :=ฉัน
  • ผม :=ผม + 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