Submission #156335

#	Time	Username	Problem	Language	Result	Execution time	Memory
156335		nahid08	Palindromes (APIO14_palindrome)	C++14	47 / 100	1077 ms	12436 KiB

palindrome

/*
Nahid Hossain
Jahangirnagar University
Roll:54
*/
#include<bits/stdc++.h>
#define ll          long long int
#define db          double
#define pf          printf
#define sf          scanf
#define ff          first
#define ss          second
#define clr         clear()
#define sz          size()
#define pb          push_back
#define mk          make_pair
#define pi          acos(-1)
#define inf         1000000000000000000
//#define mod         1000000007
#define ull         unsigned long long int
#define f(i,k,n)    for(ll i=k;i<n;i++)
#define fr(i,n,k)   for(i=n;i>=k;i--)
#define ent(a)      scanf("%lld",&a)
#define ent2(a,b)   scanf("%lld%lld",&a,&b)
#define ent3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define mem(a)      memset(a,0,sizeof(a))
#define vec(v,s)    vector<ll>v[s]
#define arr(a,s)    ll a[s];
//#define check(n,pos) (n&(1<<pos))
//#define set(n,pos)  (n|(1<<pos))
//knight and king//
int dr[]={2, 2, -2, -2, 1, -1, 1, -1};
int dc[]={1,-1,  1, -1, 2,  2,-2, -2};
int dr1[]={0, 0, 0, 1, 1, 1, -1, -1, -1};
int dc1[]={-1,0, 1,-1, 0, 1, -1, 0,   1};
int dr2[]={0, 0, 1, -1};
int dc2[]={1,-1, 0,  0};
////////////////////////////
using namespace std;
#define ma 100004


string s; // 0-indexed
int t, idx, tree[ma][26], link[ma], len[ma], occ[ma], n;
void extend(int p) {
    while(s[p - len[t] - 1] != s[p]) t = link[t];
    int ch = s[p] - 'a', x = link[t];
    while(s[p - len[x] - 1] != s[p]) x = link[x];
    if(!tree[t][ch]) {
        tree[t][ch] = ++idx, len[idx] = len[t] + 2;
        link[idx] = len[idx] == 1 ? 2 : tree[x][ch];
    } t = tree[t][ch], ++occ[t];
}

void build() {
    len[1] = -1, len[2] = 0;
    link[1] = link[2] = 1;
    t = idx = 2;
    n=s.sz;
    for(int i = 0; i < n; i++) extend(i);
    for(int i = idx; i > 2; i--) {
        occ[link[i]] += occ[i];
    }
}


int main()
{
    cin>>s;

    build( );

    ll i,j,ans=0;

    for(i=3;i<=idx;i++)
    {
        ll p=len[i]*occ[i];
        ans=max(ans,p);
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:73:10: warning: unused variable 'j' [-Wunused-variable]
     ll i,j,ans=0;
          ^

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