Append to Make a Palindrome
Autumn Tournament (2011)
Submission name: symmetric.cpp
Problem summary
Append as few characters as possible to the end of a character sequence so that the resulting sequence reads identically in both directions. Print the number and the appended characters.
Source clarification. The third PDF example is inconsistent: it prints a count of 5 but displays a six-character addition for alpha21. Under the stated palindrome requirement, the correct minimum is 6 and the appended text is 2ahpla, producing alpha212ahpla. The implementation follows the requirement; the displayed example above uses the consistent repe sample.
Input
N, followed by N non-whitespace characters.
Output
The minimum number M on the first line, then the M appended characters on the next line. If M is zero, the second line is empty.
Constraints
1 ≤ N ≤ 1050.
Worked example
Original statement sample, with whitespace restored where PDF extraction merges adjacent numbers.
Input
4 repe
Output
1 r
Solution analysis
- Choose the earliest position start such that the suffix from start to the end is already a palindrome. The characters before start are the unmatched prefix; append them in reverse order.
- Test a suffix using two pointers moving inward. Trying starts 0, 1, 2 and so on ensures that the first successful suffix is the longest palindromic suffix. The final one-character suffix always works.
- For repe, the whole string is not a palindrome, but its suffix epe is. The unmatched prefix is r, so append r to obtain reper. Only one character is needed. For alabala the whole sequence is symmetric and nothing is appended.
Why it works
If k characters are appended, the original suffix after its first k characters must match its own reverse: those characters are paired internally in the final palindrome. Conversely, any palindromic suffix yields a palindrome by appending the reversed preceding prefix. Choosing the longest such suffix minimizes k.
Watch out. Append the reverse of the unmatched prefix, not the suffix. Stop at the first successful suffix. For an already symmetric input output zero and an empty second line.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
cin>>n;
string text;
for(int i=0;i<n;++i){
char symbol;
cin>>symbol;
text+=symbol;
}
int start=0;
while(start<n){
int left=start;
int right=n-1;
while(left<right&&text[left]==text[right]){
++left;
--right;
}
if(left>=right){
break;
}
++start;
}
cout<<start<<'\n';
// Mirror the prefix around the palindromic suffix.
for(int i=start-1;i>=0;--i){
cout<<text[i];
}
cout<<'\n';
}