*Cách 1 *

Trong xâu đối xứng thì vị trí ~i~ sẽ đối xứng với vị trí ~length(s)-i+1~

Do đó ta xét từng cặp kí tự ở vị trí đối xứng nhau:

• Nếu kí tự ở vị trí ~i~ và kí tự ở vị trí đối xứng là ~length(s)-i+1~ khác nhau và kí tự ở vị trí ~i~ và vị trí ~length(s)-i~ cũng khác nhau thì ta chèn kí tự ở vị trí thứ ~i~ vào xâu ~S~ ở vị trí ~length(s)-i+2~ và tính lại độ dài xâu, khi đó ta sẽ có kí tự thứ ~i~ và kí tự thứ ~length(s)-i+1~ sẽ giống nhau.
• Nếu kí tự ở vị trí ~i~ và kí tự ở vị trí đối xứng là ~length(s)-i+1~ khác nhau và kí tự ở vị trí ~i~ và vị trí ~length(s)-i~ giống nhau thì ta chèn kí tự ở vị trí thứ ~length(s) – i +1~ vào xâu ~S~ ở vị trí ~i~ và tính lại độ dài xâu, khi đó ta sẽ có kí tự thứ ~i~ và kí tự thứ ~length(s)-i+1~ sẽ giống nhau, kí tự ở vị trí ~i+1~ và ~lengh(s)-i~ cũng giống nhau.

Ví dụ: ~S=~TOMATO

Ở vị trí ~i=1~: kí tự ở vị trí ~i~ và vị trí đối xứng là ~length(s) –i +1~ khác nhau; kí tự ở vị trí ~i~ và kí tự ở vị trí ~length(s)-i~ giống nhau. Khi đó cần chèn kí tự O vào vị trí ~1~ để được xâu mới, khi đó ta có cặp kí tự đối xứng.

Cách 2.

Có thể giải bài toán bằng thuật toán quy hoạch động.

Gọi ~C[i,j]~ là số kí tự ít nhất cần thêm vào để xâu ~S[i..j]~ là xâu đối xứng. Ta có công thức truy hồi như sau:

• Nếu ~S[i] = S[j]~ thì ~C[i,j] = C[i+1,j-1]~
• Ngược lại: ~C[i,j] := min(C[i+1,j],C[i,j-1]) + 1~ (cộng ~1~ kí tự ~S[i]~ hoặc ~S[j]~ thêm vào xâu ~S[i..j]~)

*Cách 3: *

Gọi ~S2~ là xâu đảo của xâu ~ST~ ban đầu, ~T~ là xâu con chung của hai xâu ~S2~ và ~ST~. Khi đó các kí tự của ~ST~ không thuộc ~T~ chính là các kí tự cần chèn vào xâu ~ST~ để ~ST~ trở thành xâu đối xứng. Bài toán trở thành bài toán tìm dãy con chung dài nhất của hai xâu bằng phương pháp quy hoạch động.