Cho hai chuỗi s và t (chỉ chứa chữ cái thường). Tìm tiền tố chung dài nhất p, phần còn lại của s là s', của t là t'. Trả về danh sách 3 cặp [(len(p), p), (len(s'), s'), (len(t'), t')].
Ví dụ: s = "science", t = "school" → [(2, 'sc'), (5, 'ience'), (4, 'hool')].
Thuật toán
- Duyệt đồng thời hai chuỗi cho đến khi gặp ký tự khác nhau hoặc hết chuỗi ngắn hơn.
- Gộp các ký tự chung vào
lcp(Longest Common Prefix). - Cắt phần còn lại:
s_rem = s[len(lcp):],t_rem = t[len(lcp):]. - Trả về list 3 tuple như mô tả.
Ví dụ mã nguồ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)) # [(2, 'sc'), (5, 'ience'), (4, 'hool')]
Đầu vào / Đầu ra
Input: "science", "school"
Output: [(2, 'sc'), (5, 'ience'), (4, 'hool')]