➤ Problem Link : 1326D2. Prefix
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define m 998244353
int longest_palindrome_prefix(const string &s)
{
string kmprev = s;
std::reverse(kmprev.begin(), kmprev.end());
string kmp = s + "#" + kmprev;
vector<int> lps(kmp.size(), 0); // lps[i] = longest suffix length for substring kmp[0..i] where the suffix == prefix
for (int i = 1; i < (int)lps.size(); ++i)
{
int prev_idx = lps[i - 1];
while (prev_idx > 0 && kmp[i] != kmp[prev_idx])
{
prev_idx = lps[prev_idx - 1];
}
lps[i] = prev_idx + (kmp[i] == kmp[prev_idx] ? 1 : 0);
}
// after KMP's LPS preprocessing, the last index of the LPS array will contain the longest palindrome prefix' length!
return lps[lps.size() - 1];
}
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int n=s.length();
int j=0;
while(j<n-j-1 && s[j]==s[n-j-1])
j++;
if(j==n-j-1)
{
cout<<s<<endl;
continue;
}
string t=s.substr(j,n-j-1-j+1);
int len=longest_palindrome_prefix(t);
string mid="";
if(len>0)
{
mid=t.substr(0,len);
}
reverse(t.begin(),t.end());
int l2=longest_palindrome_prefix(t);
if(l2>len)
mid=t.substr(0,l2);
// cout<<dp[2][3]<<endl;
// cout<<j<<" "<<pi<<" "<<pj<<endl;
string ans="";
ans+=s.substr(0,j);
ans+=mid;
ans+=s.substr(n-j,j);
cout<<ans<<endl;
}
}
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!!
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.