a146. 最長回文子序列 - 旦旦解題農場

內容

如果一個字串，將其反轉後與原字串相同，則稱該字串為回文，例如a,abcba,abba皆為回文，但abc,abcab不是回文。

一個字串的子序列為該字串中刪掉一些字元後所產生的字串，例如a,abc,aba,aa,bca等皆為abca的子序列，但cb,aaa,bac不是其子序列。

一個字串的子序列若恰好又是回文則稱為回文子序列，而一個字串的所有回文子序列中，最長的則稱作最長回文子序列。

請寫一個程式找出一個字串的最長回文子序列長度為何?

輸入說明

多筆測資，讀到EOF結尾。

每筆測資輸入一個字串。

保證單個測資點的字串長度總和不超過10000，且字串僅包含小寫英文字母。

輸出說明

每筆測資輸出最長回文子序列的長度。

範例輸入

abc
abacbc
aabbccaba

範例輸出

1
3
6

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 1.0s , <1M
公開測資點#4 (10%): 1.0s , <1M
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1M
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <1M

提示：

標籤:

出處:

[管理者：

giver (垃圾)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」