418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 7
ไปยังการนำทาง
ไปยังการค้นหา
ให้ เป็นความยาวที่มากที่สุดของ common subsequence ของ และ
![{\displaystyle x[1...i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83d18531fd7f0196254e395585cc495a286ac17a)
![{\displaystyle y[1...j]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/878a220e465a287b5310f4cfc6d0925882b696a2)
แนวคิดจะทำการพิจารณาว่าตัวอักษร ตรงกับตัวอักษร หรือไม่ ถ้าตรงแสดงว่าเราได้ common subsequence มาแล้วหนึ่งตัว แต่ถ้าไม่ตรง อาจเป็นไปได้ที่ตัวอักษร นี้ไปตรงกับตัวอักษรที่ หรือ ตัวอักษร ไปตรงกับตัวอักษร ซึ่งการที่เราจะเลือกกรณีไหน ก็ขึ้นอยู่กับว่ากรณีนั้นต้องมี common subsequence ยาวที่สุด ดังนั้นเราจะได้ว่า
ถ้า หรือ
ถ้า
ถ้า
เขียนเป็น pseudocode ได้ดังนี้
<geshi lang="c"> LCS(x,n,y,m)
for i=1 to n do
M[i,0] = 0
for j=1 to m do
M[0,j] = 0
for i = 1 to n do
for j = 1 to m do
if x[i] = y[j] then
M[i,j] = 1+M[i-1,j-1]
else
M[i,j] = max(M[i-1,j],M[i,j-1])
return M[n,m]
</geshi>
เห็นได้ชัดว่าอัลกอริทึมข้างต้นใช้เวลาทำงานเป็น
