สมมติว่าเรามีสตริงสองตัว s และ t (ทั้งคู่มีเฉพาะตัวอักษรภาษาอังกฤษพิมพ์เล็ก) เราต้องหาคู่ของรายการขนาด 3 โดยแต่ละคู่มีรูปแบบ (l, k) โดย k คือสตริง และ l คือความยาวของมัน สามคู่นี้ประกอบด้วย: คู่อันแรกมีสตริงย่อยที่เป็นคำนำหน้าร่วมที่ยาวที่สุด (Longest Common Prefix) p ของ s และ t ส่วนที่เหลือของ s คือ s' และของ t คือ t' รายการสุดท้ายจะเป็น [(ความยาวของ p, p), (ความยาวของ s', s'), (ความยาวของ t', t')]
ตัวอย่างเช่น หาก s = "science" t = "school" ผลลัพธ์จะเป็น [(2, 'sc'), (5, 'ience'), (4, 'hool')]
ขั้นตอนการแก้ปัญหา
- lcp := สตริงว่าง
- for i ในช่วง 0 ถึง min(len(s), len(t)):
- ถ้า s[i] เท่ากับ t[i]: lcp := lcp + s[i]
- s_rem := สตริงย่อยของ s จากดัชนี (ความยาวของ lcp) ถึงท้าย
- t_rem := สตริงย่อยของ t จากดัชนี (ความยาวของ lcp) ถึงท้าย
- คืนค่ารายการสามคู่ [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)]
ตัวอย่างโค้ด
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))
อินพุต
"science", "school"
เอาต์พุต
[(2, 'sc'), (5, 'ience'), (4, 'hool')]
