e595 - 11475 - Extend to Palindrome
題目描述
題目要求對於給定的字串，找到最小的迴文字串，其可以通過在原字串末尾添加最少數量的字元來形成。
解題思路
程式碼的思路是遍歷字串的所有前綴，檢查從該前綴開始到字串結尾的部分是否為迴文。如果找到一個迴文前綴，則將字串反轉並附加到字串的末尾，以形成最小的迴文。由於題目要求找到 最小 的迴文，因此從字串的開頭開始尋找最長的迴文後綴是合理的。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int sl;
string s;
bool isrev(int l,int r){
for(int i=l,j=0;i<=r;++i,++j){
if(s[i]!=s[r-j])return 0;
}
return 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> s){
sl=s.length();
for(int i=0;i<sl;++i){
if(isrev(i,sl-1)){
cout << s;
for(int j=i-1;j>=0;--j){
cout << s[j];
}
cout << "\n";
break;
}
}
}
}