Chương trình tìm tổng số điểm tương đồng của một chuỗi và các chuỗi con của nó bằng Python

Giả sử chúng ta có một chuỗi s. Chúng ta phải tìm tổng các điểm tương đồng của chuỗi s với mỗi chuỗi của nó. Ở đây điểm giống nhau giữa hai chuỗi là độ dài của chuỗi toboth chung tiền tố dài nhất.

Vì vậy, nếu đầu vào là s =​​"pqpqpp", thì đầu ra sẽ là 11 vì các hậu tố của chuỗi là "pqpqpp", "qpqpp", "pqpp", "qpp", "pp" và "p". Điểm giống nhau của các chuỗi con này với chuỗi "pqpqpp" là 6,0,3,0,1 và 1. Vì vậy, tổng là 6 + 0 + 3 + 0 + 1 + 1 =11.

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

• length:=kích thước của s
• tổng số:=chiều dài
• z:=một danh sách chứa 0 ban đầu
• l:=0, r:=0
• đối với k trong phạm vi từ 1 đến độ dài - 1, thực hiện
  • nếu k> r, thì
    • trận đấu:=0
    • chỉ mục:=k
  • while index
  • nếu s [chỉ số] giống với s [đối sánh] thì
    • match:=match + 1
    • index:=index + 1
  • nếu không,
    • ra khỏi vòng lặp
• chèn kết quả phù hợp vào cuối z
• nếu khớp> 0, thì
  • tổng số:=tổng số + trận đấu
  • l:=k
  • r:=index-1
• nếu không,
  • nếu z [k-l] <(r-k) +1, thì
    • chèn z [k-l] vào cuối z
    • tổng số:=total + z [k-l]
  • nếu không,
    • trận đấu:=r-k
    • index:=r
    • while index
    • nếu s [chỉ số] giống với s [đối sánh] thì
      • match:=match + 1
      • index:=index + 1
    • nếu không,
      • ra khỏi vòng lặp
  • chèn kết quả phù hợp vào cuối z
  • tổng số:=tổng số + trận đấu
  • l:=k
  • r:=index-1

Ví dụ

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

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

Đầu vào

"pqpqpp"

Đầu ra

11