切換
舊版
前往
大廳
主題

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

Not In My Back Yard | 2020-01-09 23:04:09 | 巴幣 0 | 人氣 465
題目連結：
題目大意：
給定一由大寫以及小寫字母組成的字串（長度 ≦ 100000）。請藉由在該尾端補上 0 個以上（含）的字元，使字串變成一個迴文。加的字元要越少越好。

範例輸入：
aaaa
abba
amanaplanacanal
xyz
範例輸出：
aaaa
abba
amanaplanacanalpanama
xyzyx
解題思維：
如果給定的字串（以下稱 S ）已經是迴文了，那麼就不用加上任何字元輸出。相似地，如果 S 中有以其最後一個字元結尾的最長迴文子字串存在，則只需要在結尾反著新增那些不是該迴文裡的字元再輸出即可。

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

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

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#字串#窮舉
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

經典不敗

看更多

相關創作

更多創作

追蹤 創作集
其他創作
作品資料夾