主題

ZeroJudge - e595: 11475 - Extend to Palindrome　解題心得

Not In My Back Yard | 2020-01-09 23:04:09 | 巴幣 0 | 人氣 578

題目連結(jié)：

題目大意：

給定一由大寫以及小寫字母組成的字串（長度 ≦ 100000）。請藉由在該尾端補(bǔ)上 0 個以上（含）的字元，使字串變成一個迴文。加的字元要越少越好。

範(fàn)例輸入：

aaaa

abba

amanaplanacanal

xyz

範(fàn)例輸出：

aaaa

abba

amanaplanacanalpanama

xyzyx

解題思維：

如果給定的字串（以下稱 S ）已經(jīng)是迴文了，那麼就不用加上任何字元輸出。相似地，如果 S 中有以其最後一個字元結(jié)尾的最長迴文子字串存在，則只需要在結(jié)尾反著新增那些不是該迴文裡的字元再輸出即可。

例如範(fàn)例測資中的 amanaplanacanal 可以看到，其中的藍(lán)色部分amanaplanacanal 就是一個最長的迴文子字串。因此只需要新增 amanap 的相反字串 —— panama 到尾端即是所求。

所以每輸入一個 S 就窮舉每個位置看看是否以該字元為迴文的開頭並以 S 的最後一個字元作結(jié)尾。如此一來需要新增的字元即是最少的。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

ETH官方钱包