กุญแจลับสมบัติเก้าเส้ง

toi12_key

เรียกรหัสลับของน้องสิงหลาว่า S1S_1 รหัสลับของน้องสิงขรว่า S2S_2 และสตริงที่เราต้องการถามว่าสร้างได้หรือไม่ว่า TT

ให้ f(i,j)f(i, j) เท่ากับ 11 ถ้าเราสามารถใช้ S1[i,m1]S_1[i, m-1] และ S2[j,n1]S_2[j, n-1] ไขว้กันเพื่อสามารถสร้าง T[i+j,m+n1]T[i+j, m+n-1] ได้ มิเช่นนั้นจะให้เท่ากับ 00

สามารถคำนวณ f(i,j)f(i, j) โดย dynamic programming ตามความสัมพันธ์ดังนี้

  • f(m,n)=1f(m, n) = 1
  • f(i,j)=(S1[i]==T[i+j] and f(i+1,j)) or (S2[j]==T[i+j] and f(i,j+1))f(i, j) = (S_1[i] == T[i+j]\ and\ f(i+1, j))\ or\ (S_2[j] == T[i+j]\ and\ f(i, j+1))

เราจะตอบ YES ก็ต่อเมื่อ f(0,0)=1f(0, 0) = 1 เท่านั้น ดังนั้นเราจะได้อัลกอริธึมที่แก้ปัญหานี้ใน O(nmk)\mathcal{O}(nmk)