ข้อ 2 · LC1071 Greatest Common Divisor of Strings 🟡

ขั้นที่ 1 · โจทย์นี้ขออะไรจริง ๆ

คำว่าหารในข้อนี้ไม่ใช่การหารเลข แต่เป็นนิยามที่โจทย์ตั้งขึ้นเอง ให้นึกภาพเป็นตัวต่อเลโก้ชิ้นเดียวกัน

ถ้า str1 คือแถวที่ต่อจากเลโก้ชิ้น AB จำนวน 3 ชิ้น และ str2 คือแถวที่ต่อจากชิ้น AB จำนวน 2 ชิ้น แปลว่าทั้งสองแถวใช้เลโก้ชิ้นเดียวกัน

โจทย์ถามหาเลโก้ชิ้นที่ ใหญ่ที่สุด ที่ต่อเป็นทั้งสองแถวได้ ไม่ใช่ชิ้นเล็กสุด

ขั้นที่ 2 · ความเชื่อผิดสองข้อที่ต้องเคลียร์ก่อน

ความเชื่อผิดข้อแรกคือ คำตอบต้องเป็นสตริงที่สั้นกว่าเสมอ ลองดูว่าจริงไหม

import math

def wrong(a, b):
    return b if len(b) <= len(a) else a

def right(a, b):
    if a + b != b + a:
        return ""
    return a[:math.gcd(len(a), len(b))]

for a, b in [("ABCABC","ABC"), ("ABABAB","ABAB"), ("LEET","CODE")]:
    print(f"str1={a!r} str2={b!r} | เดาว่าตัวสั้นกว่า -> {wrong(a,b)!r} | คำตอบจริง -> {right(a,b)!r}")

str1='ABCABC' str2='ABC' | เดาว่าตัวสั้นกว่า -> 'ABC' | คำตอบจริง -> 'ABC'
str1='ABABAB' str2='ABAB' | เดาว่าตัวสั้นกว่า -> 'ABAB' | คำตอบจริง -> 'AB'
str1='LEET' str2='CODE' | เดาว่าตัวสั้นกว่า -> 'CODE' | คำตอบจริง -> ''

บรรทัดแรกถูกโดยบังเอิญ แต่บรรทัดที่สองผิด เพราะ ABAB หาร ABABAB ไม่ได้ (6 หารด้วย 4 ไม่ลงตัว) ต้องถอยลงมาเป็น AB

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

ความเชื่อผิดข้อที่สองคือ ยิ่งสั้นยิ่งปลอดภัย ซึ่งก็ไม่ใช่ เพราะโจทย์ขอตัวที่ยาวที่สุด ตอบสั้นเกินไปก็ผิด

ขั้นที่ 3 · วิธีตรงไปตรงมาที่ใช้ได้จริง

จากความยาวข้างบน เราได้เบาะแสว่าความยาวของบล็อกต้องหารความยาวของทั้งสองสตริงลงตัว

ความยาวที่หารทั้งคู่ลงตัวและใหญ่ที่สุด คือ ห.ร.ม. ของสองความยาว ดังนั้นเราไม่ต้องไล่ลองทุกความยาวเลย มีตัวเลือกเดียว

import math

for a, b in [("ABCABC","ABC"), ("ABABAB","ABAB"), ("ABABABAB","ABAB"), ("LEET","CODE")]:
    g = math.gcd(len(a), len(b))
    print(f"str1={a!r}({len(a)}) str2={b!r}({len(b)}) -> gcd={g} -> ตัวเลือกคำตอบ = str1[:{g}] = {a[:g]!r}")

str1='ABCABC'(6) str2='ABC'(3) -> gcd=3 -> ตัวเลือกคำตอบ = str1[:3] = 'ABC'
str1='ABABAB'(6) str2='ABAB'(4) -> gcd=2 -> ตัวเลือกคำตอบ = str1[:2] = 'AB'
str1='ABABABAB'(8) str2='ABAB'(4) -> gcd=4 -> ตัวเลือกคำตอบ = str1[:4] = 'ABAB'
str1='LEET'(4) str2='CODE'(4) -> gcd=4 -> ตัวเลือกคำตอบ = str1[:4] = 'LEET'

บรรทัดสุดท้ายเตือนเราว่า ห.ร.ม. บอกได้แค่ความยาวที่เป็นไปได้ ไม่ได้รับประกันว่าบล็อกนั้นใช้ได้จริง จึงยังต้องเช็คอีกชั้น

import math

def divides(block, s):
    return len(s) % len(block) == 0 and block * (len(s) // len(block)) == s

for a, b in [("ABCABC","ABC"), ("ABABAB","ABAB"), ("ABABABAB","ABAB"), ("LEET","CODE")]:
    g = math.gcd(len(a), len(b))
    cand = a[:g]
    print(f"str1={a!r} str2={b!r} | ลอง {cand!r}: หาร str1 ได้? {divides(cand,a)} หาร str2 ได้? {divides(cand,b)}")

str1='ABCABC' str2='ABC' | ลอง 'ABC': หาร str1 ได้? True หาร str2 ได้? True
str1='ABABAB' str2='ABAB' | ลอง 'AB': หาร str1 ได้? True หาร str2 ได้? True
str1='ABABABAB' str2='ABAB' | ลอง 'ABAB': หาร str1 ได้? True หาร str2 ได้? True
str1='LEET' str2='CODE' | ลอง 'LEET': หาร str1 ได้? True หาร str2 ได้? False

ขั้นที่ 4 · ทางลัดที่สั้นกว่า และเหตุผลที่มันใช้ได้

มีวิธีเช็คที่สั้นกว่า divides คือเช็คว่า str1 + str2 เท่ากับ str2 + str1 ไหม

ทิศทางที่เข้าใจง่ายก่อน: ถ้าสองสตริงสร้างจากบล็อกเดียวกันจริง ต่อสลับข้างย่อมได้ผลเหมือนกัน เพราะทั้งสองฝั่งก็แค่บล็อกเดิมมาเรียงต่อกันจำนวนรวมเท่ากัน

ทิศทางกลับกันคือส่วนที่ลึกกว่า: ถ้า str1 + str2 เท่ากับ str2 + str1 แล้วรับประกันได้ว่ามีบล็อกร่วมอยู่จริง ข้อนี้เป็นทฤษฎีบทที่พิสูจน์แล้วในทฤษฎีสตริง เราขอไม่พิสูจน์ที่นี่