➤ 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!!