Prepend to Make a Palindrome
Autumn Tournament (2016)
Submission name: palin.cpp
Problem summary
A non-palindromic lowercase string is given. Add letters only to its left to obtain a palindrome, and find the minimum possible final length.
Input
One nonempty lowercase string.
Output
The minimum length after prepending letters.
Constraints
0 < N < 500,000; the input is not already a palindrome.
Worked example
Official statement sample.
Input
babaa
Output
7
Solution analysis
- Let L be the longest palindromic prefix of the original string s. Reverse the remaining suffix and prepend it: the prefix remains a palindrome and the two copies of the suffix mirror one another. This produces length 2N − L.
- Find L in linear time using the prefix function of s + "#" + reverse(s). A border of this combined string matches a prefix of s with the reverse of that same prefix, so the last prefix-function value is exactly the longest palindromic prefix. The separator cannot occur in the input and prevents matches crossing the boundary.
- For babaa, the longest palindromic prefix is bab, of length 3. The remaining suffix is aa. Prepending its reverse gives aababaa, of length 2·5 − 3 = 7. The code builds the prefix-function array with failure links rather than repeatedly testing prefixes.
Why it works
Suppose k < N letters are prepended. In the final palindrome, the initial N−k letters of s must pair among themselves, so they form a palindromic prefix. Thus N−k ≤ L and the final length N+k ≥ 2N−L. Prepending the reversed suffix of length N−L attains that bound.
Watch out. Do not confuse the longest palindromic prefix with the longest palindrome anywhere in the string. The order s + separator + reverse(s) matters. The input guarantee excludes an already-palindromic string.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
string text;
cin>>text;
string reversed=text;
reverse(reversed.begin(),reversed.end());
string combined=text+"#"+reversed;
vector<int>prefix(combined.size(),0);
for(int i=1;i<static_cast<int>(combined.size());i++){
int matched=prefix[i-1];
// Follow shorter borders until the next characters can match.
while(matched>0&&combined[i]!=combined[matched]){
matched=prefix[matched-1];
}
if(combined[i]==combined[matched]){
matched++;
}
prefix[i]=matched;
}
cout<<2*text.size()-prefix.back()<<'\n';
}