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

สมมติว่าเรามีสตริง s เราต้องหาผลรวมของความเหมือนของสตริง s กับคำต่อท้ายแต่ละคำ ความคล้ายคลึงกันระหว่างสองสตริงคือความยาวของคำนำหน้าที่ยาวที่สุดทั่วไปของสตริงทั้งสอง

ดังนั้น หากอินพุตเป็น s ="pqpqpp" เอาต์พุตจะเป็น 11 เนื่องจากส่วนต่อท้ายของสตริงคือ "pqpqpp", "qpqpp", "pqpp", "qpp", "pp" และ "p" ความคล้ายคลึงกันของสตริงย่อยเหล่านี้กับสตริง "pqpqpp" คือ 6,0,3,0,1 และ 1 ดังนั้นผลรวมคือ 6 + 0 + 3 + 0 + 1 + 1 =11

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

• ความยาว :=ขนาด s
• รวม :=ความยาว
• z :=รายการที่มี 0 เริ่มแรก
• l :=0, r :=0
• สำหรับ k ในช่วง 1 ถึงความยาว - 1 ทำ
  • ถ้า k> r แล้ว
    • จับคู่:=0
    • ดัชนี :=k
  • ในขณะที่ดัชนี <ความยาว ทำ
    • ถ้า s[index] เหมือนกับ s[match] แล้ว
      • จับคู่ :=จับคู่ + 1
      • ดัชนี :=ดัชนี + 1
    • มิฉะนั้น
      • ออกมาจากลูป
  • แทรกการจับคู่ที่ส่วนท้ายของ z
  • ถ้าตรงกัน> 0 แล้ว
    • รวม :=รวม + ตรงกัน
    • l :=k
    • r :=index-1
  • มิฉะนั้น
    • ถ้า z[k-l] <(r-k)+1 แล้ว
      • แทรก z[k-l] ที่ส่วนท้ายของ z
      • ผลรวม :=รวม + z[k-l]
    • มิฉะนั้น
      • match :=rk
      • ดัชนี :=r
      • ในขณะที่ดัชนี <ความยาว ทำ
        • ถ้า s[index] เหมือนกับ s[match] แล้ว
          • จับคู่ :=จับคู่ + 1
          • ดัชนี :=ดัชนี + 1
        • มิฉะนั้น
          • ออกมาจากลูป
      • แทรกการจับคู่ที่ส่วนท้ายของ z
      • รวม :=รวม + ตรงกัน
      • l :=k
      • r :=index-1
• ผลตอบแทนรวม

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(s):
   length = len(s)
   total = length

   z = [0]
   l = 0
   r = 0

   for k in range(1,length):
      if k > r:
         match=0
         index = k
         while index < length:
            if s[index] == s[match]:
               match +=1
               index +=1
            else:
               break
         z.append(match)
         if match > 0:
            total+=match
            l = k
            r = index-1
      else:
         if z[k-l] < (r-k)+1:
            z.append(z[k-l])
            total+=z[k-l]
         else:
            match = r-k
            index = r
            while index < length:
               if s[index] == s[match]:
                  match +=1
                  index +=1
               else:
                  break
            z.append(match)
            total+=match
            l = k
            r = index-1
   return total

s = "pqpqpp"
print(solve(s))

อินพุต

"pqpqpp"

ผลลัพธ์

11