qwertsboy1234's blog

By qwertsboy1234, history, 4 weeks ago, In English

I am getting tle in this problem of cses Longest Pallindrome.Can anyone suggest me some optimisation . MY LOGIC: I maintained hash values for the string and for the reverse of it.Then i am doing binary search checking for values from i=1 to i=n. Example: for example if our string is abyuuy then maintain hash values for abyuuy and maintain hash values for yuuyba.Then while oing binary search from 1 to let say we are at 4 then i will start checking from i=0 and at i=2 i found (using hash values) that its pallindrome so i found it,You can understand it more from my code Effectively the complexity is o(nlogn) but its giving tle. Here is my code

#include<bits/stdc++.h>
using namespace std;
#define dd double
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define pr pair<ll,ll>
#define pri pair<pr,ll>
#define pir pair<ll,pr>
#define ppr pair<pr,pr>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll INF=1e8;
ll mod=1e9+9;
ll power(ll x,ll y,ll m)
{
    ll res=1;
    x = x%m;
    if(x==0)
    return 0;
    while(y>0)
    {
        if(y&1)
            res = (res*x)%m;

        y = y>>1;
        x = (x*x)%m;
    }

    return res%m;
}
ll modInverse(ll n,ll p)
{
    return power(n,p-2,p);
}
pr check(string &str1,vector<ll> &h,vector<ll> &p,vector<ll> &h1,vector<ll> &p1,ll val)
{
    // cout<<val<<endl;
    pr ans=mp(-1ll,-1ll);
    ll n=str1.length(),i,j,t;
    if(val==1)
    {
      ans=mp(0ll,0ll);
      return ans;
    }
    for(i=0;i<=n-val;i++)
    {
       if(val%2!=0)
       {
          ll t1,t2,val1,val2;
          t1=i,t2=i+val/2-1;
          if(i==0)
          {
            val1=h[t2];
          }
          else
          {
            val1=(h[t2]-h[t1-1]+2*mod)%mod;
            val1=(val1*modInverse(p[t1],mod))%mod;
          }
          t1=t2+2;
          t2=t1+val/2-1;
          t1=n-1-t1;
          t2=n-1-t2;
          swap(t1,t2);
          if(t1==0)
          {
            val2=h1[t2];
          }
          else
          {
            val2=(h1[t2]-h1[t1-1]+2*mod)%mod;
            val2=(val2*modInverse(p1[t1],mod))%mod;
          }
          if(val1==val2)
          {
            ans=mp(i,i+val-1);
            return ans;
          }
       }
       else
       {
          ll t1,t2,val1,val2;
          t1=i,t2=i+val/2-1;
          if(i==0)
          {
            val1=h[t2];
          }
          else
          {
            val1=(h[t2]-h[t1-1]+2*mod)%mod;
            val1=(val1*modInverse(p[t1],mod))%mod;
          }
          t1=t2+1,t2=t1+val/2-1;
          t1=n-1-t1;
          t2=n-1-t2;
          swap(t1,t2);
          if(t1==0)
          {
            val2=h1[t2];
          }
          else
          {
            val2=(h1[t2]-h1[t1-1]+2*mod)%mod;
            val2=(val2*modInverse(p1[t1],mod))%mod;
          }
          if(val1==val2)
          {
            ans=mp(i,i+val-1);
            return ans;
          }
       }
    }
    return ans;
}
int main()
{
   #ifndef ONLINE_JUDGE
   freopen("inp.txt","r",stdin);
   freopen("otpt.txt","w",stdout);
   #endif
   fastio;
   ll te=1;
   // cin>>te;
   while(te--)
   {
      string str1;
      cin>>str1;
      ll n=str1.length(),i,j,t;
      vector<ll> h(n),p(n),h1(n),p1(n);
      h[0]=str1[0]-'a';
      p[0]=1;
      ll a=31,b=1e9+9;
      for(i=1;i<n;i++)
      {
        p[i]=(p[i-1]*a)%b;
        h[i]=(h[i-1]+(str1[i]-'a')*p[i])%b;
      }
      string str2=str1;
      reverse(str2.begin(),str2.end());
      h1[0]=str2[0]-'a';
      p1[0]=1;
      for(i=1;i<n;i++)
      {
        p1[i]=(p1[i-1]*a)%b;
        h1[i]=(h1[i-1]+(str2[i]-'a')*p1[i])%b;
      }
      ll l=1,r=n;
      pr pr1,pr2,ans;
      ans=mp(0,0);
      while(l+1<r)
      {
          ll midi=(l+r)/2;
          //cout<<midi<<endl;
          pr1=check(str1,h,p,h1,p1,midi);
          pr2=check(str1,h,p,h1,p1,midi+1);
          if(pr1.fi==-1&&pr2.fi==-1)
          {
             r=midi-1;
          }
          else
          {
            if(pr2.fi!=-1)
            {
               l=midi+1;
            }
            else
            {
               l=midi;
            }
            if(ans.sc-ans.fi+1<pr1.sc-pr1.fi+1)
            {
              ans=pr1;
            }
            if(ans.sc-ans.fi+1<pr2.sc-pr2.fi+1)
            {
              ans=pr2;
            }
          }
      }
      if(l+1==r)
      {
        pr1=check(str1,h,p,h1,p1,r);
        if(ans.sc-ans.fi+1<pr1.sc-pr1.fi+1)
        {
            ans=pr1;
        }
      }
      for(i=ans.fi;i<=ans.sc;i++)
      {
        cout<<str1[i];
      }
      cout<<endl;
   }
}

Last time i wrote one such blog ,people came and upvoted and downvoted depending on their mood but noone replied,if you want to downvote me you can do that but plz help me in my problem. Any help is welcome.Thanks.

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hmm maybe you need the Manacher's algorithm