Submission #140065

#	Time	Username	Problem	Language	Result	Execution time	Memory
140065		shamimjucse	Palindromes (APIO14_palindrome)	C++14	100 / 100	70 ms	36408 KiB

palindrome

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

const int mx = 300005;
int tr[mx][26], node;
int len[mx], link[mx],suff;
string s; /// 1-indexed
int cnt[mx],occ[mx];
inline void Insert(int p)
{
    while(s[p - len[suff] - 1] != s[p])
        suff = link[suff];
    int x = link[suff], c = s[p] - 'a';
    while(s[p - len[x] - 1] != s[p])
        x = link[x];
    if(!tr[suff][c])
    {
        tr[suff][c] = ++node;
        len[node] = len[suff] + 2;
        link[node] = (len[node] == 1) ? 2 : tr[x][c];
        cnt[node]+=1 + cnt[link[node]];
    }
    suff = tr[suff][c];
    occ[suff]++;
}
void initTree()
{
    node = 2, suff = 2;
    len[1] = -1, link[1] = 1;
    len[2] = 0, link[2] = 1;
}
ll totalpalindreme = 0;
void buildTree()
{
    initTree();
    s = "#" + s;
    for(int i=1;i<s.size();i++)
    {
        Insert(i);
        totalpalindreme+=cnt[suff];
    }
}
ll countPalindromes()
{
    ll sum = 0;
    for(int i=node;i>2;i--)
    {
        occ[link[i]]+=occ[i];
        sum = max(sum,1LL*occ[i]*len[i]);
    }
    return sum;
}
int main()
{
    cin >> s;
    buildTree();
    //cout << totalpalindreme << endl;
    cout << countPalindromes() << endl;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void buildTree()':
palindrome.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<s.size();i++)
                 ~^~~~~~~~~

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