Submission #111427

#	Time	Username	Problem	Language	Result	Execution time	Memory
111427		aleksami	Palindromes (APIO14_palindrome)	C++14	0 / 100	1056 ms	41920 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;
#define MAXN 300005
#define LOG 20
typedef long long ll;
const ll p1 = 131;
const ll MOD = 1e9+7;
int n;
string s;
struct entry {
  int rnk[2];
  int idx;
};
entry order[MAXN];
int rmq[MAXN][LOG];
int suffixarray[MAXN];
int lcp[MAXN];
bool cmp(entry a,entry b){return a.rnk[0]==b.rnk[0] ? (a.rnk[1]<b.rnk[1]):(a.rnk[0]<b.rnk[0]); }
int now;

void build_suffixarray()
{
  now=1;
  for(int i = 0; i < n; i++)rmq[i][0]=s[i]-'a';
  for(int l = 1; l <  n; now++,l*=2)
  {
    for(int i = 0; i < n; i++)
    {
      order[i].rnk[0]=rmq[i][now-1];
      order[i].rnk[1]=(i+l<n)?rmq[i+l][now-1]:-1;
      order[i].idx=i;
    }
    sort(order,order+n,cmp);
    for(int i = 0; i < n; i++)
    {
      rmq[order[i].idx][now]=( i > 0 && order[i].rnk[0] == order[i-1].rnk[0] && order[i].rnk[1] == order[i-1].rnk[1] ) ? rmq[order[i-1].idx][now] : i;
    }
  }
  for(int i = 0; i < n; i++)suffixarray[rmq[i][now-1]]=i;
}
int calc_lcp(int a,int b)
{
  int ret = 0;
  for(int j = now-1; j >= 0; j--)
  {
    if(rmq[a][j]==rmq[b][j])a+=(1<<j),b+=(1<<j),ret+=(1<<j);
  }
  return ret;
}
void build_lcparray()
{
  for(int i = 0; i < n-1; i++)
  {
    lcp[i]=calc_lcp(suffixarray[i],suffixarray[i+1]);
  }
  for(int i = 0; i < n-1; i++)rmq[i][0]=lcp[i];
  for(int j = 1; j < LOG; j++)for(int i = 0; i < n; i++)if(i+(1<<j)<n)rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<j)][j-1]);
}

ll pw[MAXN];
ll invpw[MAXN];
ll sum[MAXN];
ll revsum[MAXN];
ll maxodd[MAXN];
ll maxeven[MAXN];
ll mulmod(ll x,ll y){x*=y;x%=MOD;return x;}
ll addmod(ll x,ll y){x+=y;x+=2*MOD;x%=MOD;return x;}
ll fastpow(ll x,int s)
{
  if(s==0)return 1LL;
  if(s%2==0)
  {
    ll y = fastpow(x,s/2);
    return mulmod(y,y);
  }
  return mulmod(x,fastpow(x,s-1));
}
ll geth(ll x,int s)
{
  return mulmod(x,pw[s]);
}
ll get(int l,int r)
{
  ll ret = sum[r];
  if(l>0)ret=addmod(ret,-sum[l-1]);
  ret=mulmod(ret,invpw[l]);
  return ret;
}
ll getrev(int l,int r)
{
  ll ret = revsum[r];
  if(l>0)ret=addmod(ret,-revsum[l-1]);
  ret=mulmod(ret,invpw[n-r-1]);
  return ret;
}
bool palindrome(int l,int r){return get(l,r)==getrev(l,r);}

void calc_hash()
{
  pw[0]=1LL;
  for(int i = 1; i < MAXN; i++)pw[i]=mulmod(pw[i-1],p1);
  invpw[0]=1LL;
  ll invp = fastpow(p1,MOD-2);
  for(int i = 1; i < MAXN; i++)invpw[i]=mulmod(invpw[i-1],invp);
  for(int i = 0; i < n; i++){sum[i]=geth(s[i],i);if(i>0)sum[i]=addmod(sum[i],sum[i-1]);}
  for(int i = 0; i < n; i++){revsum[i]=geth(s[i],n-i-1);if(i>0)revsum[i]=addmod(revsum[i],revsum[i-1]);}
  for(int i = 0; i < n; i++)
  {
    ll r=1;
    int lo=1,hi=n,mid=lo+hi>>1;
    while(lo<=hi)
    {
      if(i-mid+1<0 || i+mid-1 >= n)hi=mid-1;
      else if(palindrome(i-mid+1,i+mid-1))r=mid,lo=mid+1;
      else hi=mid-1;
      mid=lo+hi>>1;
    }
    maxodd[i-r+1]=max(maxodd[i-r+1],2*r-1);
  }
  for(int i = 0; i < n; i++)
  {
    ll r=0;
    int lo=1,hi=n,mid=lo+hi>>1;
    while(lo<=hi)
    {
      if(i-mid+1 < 0 || i+mid-1+1 >= n)hi=mid-1;
      else if(palindrome(i-mid+1,i+mid-1+1))r=mid,lo=mid+1;
      else hi=mid-1;
      mid=lo+hi>>1;
    }
    if(r==0)continue;
    maxeven[i-r+1]=max(maxeven[i-r+1],2*r);
  }
}

int getlcp(int x,int y)
{
  y--;
  if(x>y)return 0;
  int d = log2(y-x+1);
  int ret = 123213231;
  ret=min(ret,rmq[x][d]);
  ret=min(ret,rmq[y-(1<<d)+1][d]);
  return ret;
}

void calc_ans()
{
  ll ans = 0LL;
  for(int i = 0; i < n; i++)
  {
    ll r=1;
    int lo=2,hi=n,mid=lo+hi>>1;
    while(lo<=hi)
    {
      if(i+mid-1>=n)hi=mid-1;
      else if(getlcp(i,i+mid-1)>=maxodd[suffixarray[i]])r=mid,lo=mid+1;
      else hi=mid-1;
      mid=lo+hi>>1;
    }
    ll r1=1;
    lo=2,hi=n,mid=lo+hi>>1;
    while(lo <= hi)
    {
      if(i-mid+1<0)hi=mid-1;
      else if(getlcp(i-mid+1,i)>=maxodd[suffixarray[i]])r1=mid,lo=mid+1;
      else hi=mid-1;
      mid=lo+hi>>1;
    }
    ans=max(ans,(r+r1-1)*maxodd[suffixarray[i]]);
  }
  for(int i = 0; i < n; i++)
  {
    ll r=1;
    int lo=2,hi=n,mid=lo+hi>>1;
    while(lo<=hi)
    {
      if(i+mid-1>=n)hi=mid-1;
      else if(getlcp(i,i+mid-1)>=maxeven[suffixarray[i]])r=mid,lo=mid+1;
      else hi=mid-1;
      mid=lo+hi>>1;
    }
    ll r1=1;
    lo=2,hi=n,mid=lo+hi>>1;
    while(lo <= hi)
    {
      if(i-mid+1<0)hi=mid-1;
      else if(getlcp(i-mid+1,i)>=maxeven[suffixarray[i]])r1=mid,lo=mid+1;
      else hi=mid-1;
      mid=lo+hi>>1;
    }
    ans=max(ans,(r+r1-1)*maxeven[suffixarray[i]]);
  }
  cout << ans;
}

void debug()
{
  for(int i = 0; i < n; i++)
  {
    cout << i << " " << maxeven[i] << " " << maxodd[i] << "\n";
  }
  for(int i = 0; i < n; i++)
  {
    for(int j = suffixarray[i]; j < s.length(); j++)
    {
      cout << s[j];
    }
    cout << "\n";
  }
  cout << "LCP: ";
  for(int i = 0; i < n; i++)
  {
    cout << lcp[i] << " ";
  }
  cout << "\n";
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> s;
  n = s.length();
  build_suffixarray();
  build_lcparray();
  calc_hash();
  //debug();
  calc_ans();
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void calc_hash()':
palindrome.cpp:111:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int lo=1,hi=n,mid=lo+hi>>1;
                       ~~^~~
palindrome.cpp:117:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       mid=lo+hi>>1;
           ~~^~~
palindrome.cpp:124:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int lo=1,hi=n,mid=lo+hi>>1;
                       ~~^~~
palindrome.cpp:130:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       mid=lo+hi>>1;
           ~~^~~
palindrome.cpp: In function 'void calc_ans()':
palindrome.cpp:154:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int lo=2,hi=n,mid=lo+hi>>1;
                       ~~^~~
palindrome.cpp:160:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       mid=lo+hi>>1;
           ~~^~~
palindrome.cpp:163:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     lo=2,hi=n,mid=lo+hi>>1;
                   ~~^~~
palindrome.cpp:169:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       mid=lo+hi>>1;
           ~~^~~
palindrome.cpp:176:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int lo=2,hi=n,mid=lo+hi>>1;
                       ~~^~~
palindrome.cpp:182:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       mid=lo+hi>>1;
           ~~^~~
palindrome.cpp:185:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     lo=2,hi=n,mid=lo+hi>>1;
                   ~~^~~
palindrome.cpp:191:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       mid=lo+hi>>1;
           ~~^~~
palindrome.cpp: In function 'void debug()':
palindrome.cpp:206:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = suffixarray[i]; j < s.length(); j++)
                                 ~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27