EPALIN - Extend to Palindrome - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : EPALIN

👉 Hint : Find longest suffix of given string which is also a prefix of reverse string

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
int F[100005];
 
void build_failure(string p, int m)
{
    F[0]=F[1]=0;
    int j;
    for(int i=2;i<=m;i++)
    {
        j=F[i-1];
        while(1)
        {
            if(p[j]==p[i-1])
            {
                F[i]=j+1;
                break;
            }
            else if(j==0)
            {
                F[i]=0;
                break;
            }
            else
                j=F[j];
        }
    }
 
}
 
int kmp(string p, string s)
{
    int n=s.length();
    int m=p.length();
    build_failure(p,m);
 
    int i=0,j=0;
 
    while(j<n)
    {
        if(p[i]==s[j])
        {
            i++;
            j++;
        }
        else if(i>0)
            i=F[i];
        else
            j++;
    }
    return i;
}
 
int main()
{
    string p,s;
    while(cin>>s)
    {
        p=s;
        reverse(p.begin(),p.end());
        memset(F,0,sizeof(F));
        int l=kmp(p,s);
        cout<<s+p.substr(l)<<"\n";
    }
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.