Append to a Palindrome
National Olympiad — Regional round
Submission name: shortage.cpp
Problem summary
Append characters only to the right of a given string so the resulting string reads identically forwards and backwards. Find the minimum number appended.
Input
One string, without whitespace.
Output
One integer: the minimum appended length.
Constraints
At most 500,000 characters; each has ASCII code 33…126.
Worked example
An independently prepared example for this explanation.
Input
abca
Output
3
Solution analysis
- Only a palindromic suffix can remain unmatched by appended characters. Therefore retain the longest palindromic suffix.
- Build reverse(s), then a delimiter outside the input alphabet, then s. Its final prefix-function value is the longest prefix of reverse(s) equal to a suffix of s.
- Such a match is exactly a palindromic suffix. Subtract its length from the original length.
Why it works
If k characters are appended, the first n−k original characters must pair with them, leaving a palindromic suffix. Conversely, reflecting the prefix before any palindromic suffix completes a palindrome. Maximizing that suffix minimizes k.
Watch out. Do not use an input character as the separator. Appending to the left is a different problem.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin>>s;
string r=s;
reverse(r.begin(),r.end());
string t=r+char(1)+s; // ASCII 1 cannot occur in the input.
vector<int>pi(t.size());
for(int i=1;i<(int)t.size();i++){
int j=pi[i-1];
while(j&&t[i]!=t[j]){
j=pi[j-1];
}
if(t[i]==t[j]){
j++;
}
pi[i]=j;
}
cout<<s.size()-pi.back()<<'\n';
}