Chương trình thực hiện nén tiền tố từ hai chuỗi trong Python

Giả sử chúng ta có hai chuỗi s và t (cả hai đều chứa các chữ cái tiếng Anh viết thường). Chúng ta phải tìm một danh sách các cặp có kích thước 3, trong đó mỗi cặp ở dạng này (l, k) ở đây k là một chuỗi và l là chiều dài của nó. Bây giờ trong số ba cặp này, cặp đầu tiên chứa chuỗi con của s và t là tiền tố p chung dài nhất trong hai chuỗi này, sau đó phần còn lại của s là s 'và phần còn lại của t là t'. Vì vậy, danh sách cuối cùng sẽ giống như [(độ dài của p, p), (độ dài của s ', s'), (độ dài của t ', t')].

Vì vậy, nếu đầu vào là s =​​"science" t ="school", thì đầu ra sẽ là [(2, 'sc'), (5, 'ience'), (4, 'hool')]

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

• lcp:=chuỗi trống
• đối với tôi trong phạm vi từ 0 đến kích thước tối thiểu là s hoặc kích thước là t, thực hiện
  • nếu s [i] giống với t [i], thì
    • lcp:=lcp + s [i]
• s_rem:=chuỗi con của s từ chỉ mục (kích thước của lcp) đến cuối
• t_rem:=chuỗi con của t từ chỉ mục (kích thước của lcp) đến hết
• trả về danh sách ba cặp [(kích thước của lcp, lcp), (kích thước của s_rem, s_rem), (kích thước của t_rem, t_rem)]

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, t):
   lcp = ''
   for i in range(min(len(s), len(t))):
      if s[i] == t[i]:
         lcp += s[i]

   s_rem = s[len(lcp):]
   t_rem = t[len(lcp):]
   return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)]

s = "science"
t = "school"
print(solve(s, t))

Đầu vào

"science", "school"

Đầu ra

[(2, 'sc'), (5, 'ience'), (4, 'hool')]