Need help in Longest Palindrome (CSES) using Manchers Algorithm

Revision en1, by decrypt_me, 2023-07-29 00:51:44

Why it is showing TLE in 3 testcases

#include<bits/stdc++.h>
using namespace std;




void helper(string str){
    string temp = "#";
    long long int n = str.length();
    // because for even length it made palindrome of odd length
    // for example   #a#b#b#a#  = length(9) while it is of length(4);
    for(long long int i =0;i<n;i++){
          temp += str[i];
          temp += "#";
    }
    
    int l = 0,r = -1;
    // taking the segment [l,r] which is palindrome 
    // then let  "ababcbaba" is palindrome and center is 'c' then for 'a'(part right of 'c' )
    // the kickstart length of palindrome same as 'a'(part left of 'c')
    long long int m = temp.length();
    vector<long long int>ans(m,0);
   for(long long int i = 0;i<temp.length();i++){
          if(i>r){
             ans[i] = 0;
          }else{
              ans[i] = min(ans[l+r-i],r-i);
          }
          while(i-ans[i]>=0 && i+ans[i]<temp.length() && temp[ans[i]+i]== temp[i-ans[i]] ){
    //             cout<<temp[i+ans[i]]<<" ";
               ans[i]++;

          }
     //     cout<<" I am answer "<<ans[i]<<endl;
          if(i+ans[i]>r){
             r = i+ans[i];
             l = i-ans[i];
          }
   }
   long long int ind = -1;
   long long int len = -1;
    for(long long int i = 0;i<ans.size();i++){
    //   cout<<ans[i]<<" ";
       if(ans[i]>len){
          len = ans[i];
          ind = i;
       }
    }
    string t = "";
    bool flag = true;
     while(len>1){
        if(flag && len%2==0){
           flag = false;
          if(temp[ind]!= '#')
           t += temp[ind];

        }else if(flag && len%2 != 0){
            flag = false;
          if(temp[ind] != '#')
            t += temp[ind];
        }else{
           if(temp[ind] != '#'){
               t = temp[ind]+ t + temp[ind];
           }
        }
         ind--;
         len--;
     }

     cout<<t<<endl;
   
}

void solve(){
    string str;
    cin>>str;
    helper(str);
}



int main(){
  solve();
  return 0;
}
Tags string, palindrome, o(n), dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English decrypt_me 2023-07-29 00:51:44 2179 Initial revision (published)