เรียกรหัสลับของน้องสิงหลาว่า S1 รหัสลับของน้องสิงขรว่า S2 และสตริงที่เราต้องการถามว่าสร้างได้หรือไม่ว่า T
ให้ f(i,j) เท่ากับ 1 ถ้าเราสามารถใช้ S1[i,m−1] และ S2[j,n−1] ไขว้กันเพื่อสามารถสร้าง T[i+j,m+n−1] ได้ มิเช่นนั้นจะให้เท่ากับ 0
สามารถคำนวณ f(i,j) โดย dynamic programming ตามความสัมพันธ์ดังนี้
- f(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))
เราจะตอบ YES
ก็ต่อเมื่อ f(0,0)=1 เท่านั้น ดังนั้นเราจะได้อัลกอริธึมที่แก้ปัญหานี้ใน O(nmk)