1326D2. Prefix - Codeforces Solution C++

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