SPOJ Problem EPALIN

Extend to Palindrome

Explanation:

This problem ask us to add minimum number of characters at the end of the string s to make it a palindrome. So, basically, we need to prepare a palindrome of minimum whose prefix should be s.

A very basic approach would be to take the reverse of the string and append it to the original string. Believe me, that's a correct solution. It would give you a palindrome, but not really a palindrome with minimum length. If still not sure, try examples 'abcd' & 'abcc'. Now, I will leave it to you to decide, if the approach is correct or not.

But, we will be working very close to the first approach we had. That is, we would be taking the reverse of original string s and appending it to the original one and then trying to form a palindrome of minimum length.

Let's take a few examples to get to a solution.

Example # 1.
original string: abcd
reverse string: dcba
palindrome after appending: abcddcba
minimum length palindrome: abcdcba

Here, we can say that, if we remove the first character from the reverse, it might work. Correct, but partially. Let's take another example.

Example # 2.
original string: abcc
reverse string: ccba
palindrome after appending: abccccba
minimum length palindrome: abccba

Looking at this example, first thing which came to my mind was, we could have had a palindrome of a smaller length, which is 'abcba'(isn't it a palindrome and also smaller than 'abccba'?). Then, what's the reason, we have 'abccba'. Just a hint. string s should be a part of palindrome.

Okay, now moving ahead, here we had to remove two characters from the reverse which contradicts the conclusions from example 1. So, there must be something else which we need to check. Let's take one more example, and we will be clear what needs to be done.

Example # 3.
original string: amanaplanacanal
reverse string: lanacanalpanama
palindrome after appending: amanaplanacanallanacanalpanama
minimum length palindrome: amanaplanacanalpanama

I guess, by now, you must have guessed, what we need to remove from the reverse string. Its the longest palindrome which is also suffix of original string or prefix of its reverse. So, going ahead with above examples.

Example # 1. Result would be 'd'.
Example # 2. Result would be 'cc'.
Example # 3. Result would be 'lanacanal'.

So, now we know what needs to be done. We need to find the longest palindrome of string s which is suffix of original string s. Now, how to find the longest suffix palindrome. We know, it would be the prefix of reverse of the string. So, do we have something which takes into consideration, the prefix as well as suffix. Yes, we do have, and that's KMP algorithm (those who are not aware, check the links provided below). Not exactly KMP algorithm, but its first part, which calculates the longest suffix which is also the prefix of the string.

So, to achieve our purpose,we take string "rev(s)+#+s" (adding a # because we only need the longest prefix of the reverse of the string and not the whole string "rev(s)+s"). The maximum length we receive is the length of palindromic suffix of the string. Now, things become easy, isn't it. I will leave further part to you to implement. You can refer the solution which I used.

KMP algorithm links.
1. Part-1: https://www.youtube.com/watch?v=GTJr8OvyEVQ&index=2&list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de
2. Part-2: https://www.youtube.com/watch?v=KG44VoDtsAA&index=1&list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de
3. http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>
#define SIZE 100005

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

int prepareLPSArray(string pattern){
    /* Returns the length of longest suffix which is also prefix of the string.
       Since, we have appended original string to its reverse, we would be able
       to get the length of longest suffix of original string which is also a 
       palindrome. Below is the basic implementation of prefix array calculation 
       used in KMP algorithm. */

    int len = pattern.length();
    vector<int> lsp(len);
    lsp[0] = 0;
    for(int j=0, i=1;i<len;i++){
        if(pattern[i] == pattern[j]){
            lsp[i] = j + 1;
            j++;
        }
        else{
            while(true){
                if(j == 0 || pattern[j] == pattern[i])
                    break;
                j = lsp[j-1];
            }
            if(pattern[j] == pattern[i]){
                lsp[i] = j + 1;
                j++;
            }
            else
                lsp[i] = 0;
        }
    }
    return lsp[len - 1];
}

string findPalin(string s){
    string res = s;
    // Obtain the reverse of string.
    string revS = string(s.rbegin(), s.rend());
    // Find the no. of chars to be appended to original string.
    int noOfChars = s.length() - prepareLPSArray(revS + "#" + s);
    // Append noOfChars from original string to the result in reverse order.
    for(int i=noOfChars - 1;i>=0;i--)
        res.append(1, s[i]);
    return res;
}

int main(){
    char str[SIZE];
    // Take input until EOF.
    while(scanf("%s", str) != EOF){
        string s = str;
        // Find minimum length for s.
        cout << findPalin(s) << endl;
    }
    return 0;
}

Any suggestions are welcome.