418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6

เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาหรือจากขวาไปซ้ายแล้วจะเหมือนกัน ดังนั้นการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ เราก็ควรตรวจสอบว่าตัวอักษรตัวแรกของทางซ้ายกับตัวอักษรตัวสุดท้ายของทางขวาเหมือนกันหรือไม่ ถ้าเหมือนแล้วจะทำอะไร และถ้าไม่เหมือนจะทำอะไร

ให้ $OPT(i,j)\,$ คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง $s[i,i+1,...,j]\,$

พิจารณากรณีที่ $i>j\,$ จะได้ว่า $OPT(i,j)=0\,$

กรณีที่ $i=j\,$ จะได้ว่า $OPT(1,1)=1\,$

ส่วนกรณีที่เหลือจะได้ว่า $OPT(i,j)=max(OPT(i+1,j),OPT(i,j-1))\,$ ถ้า $s[i]!=s[j]\,$

หรือ $OPT(i,j)=max(OPT(i+1,j),OPT(i,j-1),OPT(i+1,j-1))\,$ ถ้า $s[i]=s[j]\,$

เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c"> PALINDROMIC(s,n)

   for i = 1 to n do
       M[i,i] = 1
   for i = 2 to n do
       for j = i-1 downto 1
           M[i,j] = 0
   for i = n-1 downto 1 do
       for j = i+1 to n-1 do
           if s[i] != s[j] then
               M[i,j] = max(M[i+1,j],M[i,j-1])
           else
               M[i,j] = max(M[i+1,j],M[i,j-1],2+M[i+1,j-1])
   retrun M[1,n]

</geshi>