\(
\newcommand{\ord}[1]{\mathcal{O}\left(#1\right)}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\opord}{\operatorname{\mathcal{O}}}
\newcommand{\argmax}{\operatorname{arg\,max}}
\newcommand{\str}[1]{\texttt{"#1"}}
\)
迴文自動機
題目敘述
ㄠㄨ
卦長是一個迴文家,他寫出來的任何字串都會是迴文的形式。有天卦長發現世界上有太多字串不是迴文,不符合他的期望,所以他想請你打造一台迴文字動機,只要把字串輸入進去,他就可以在其中任意位置插入一些字符來讓它變成迴文,像是aab進入迴文字動機後會變成baab或aabaa...之類的迴文,但是每插一個字符,就會消耗你一單位的$SM$力,你要怎麼做才能讓消耗的$SM$力最小呢?
輸入說明
輸入有多行,每行有一個字串$S$
輸出說明
對於每個字串$S$輸出你最少要消耗幾單位的$SM$力才能讓它變成迴文
範例輸入
abcd
aaaa
abc
aab
abababaabababa
pqrsabcdpqrs
範例輸出
3
0
2
1
0
9
配分方法
- 0% 範例測資
- 40% $|S| \leq 100$
- 60% $|S| \leq 1000$
Hints
對於第一筆測資,消耗最少$SM$力把他們變成迴文之後如下:
abcdcba
aaaa
abcba
baab
abababaabababa
pqrsabcdpqrqpdcbasrqp
* 使用遞迴可能會過慢!
Judge Setting
run-time limit: 400 ms
memory limit: 6481920 byte
測資數量: 0