Submission #140069

#	Time	Username	Problem	Language	Result	Execution time	Memory
140069		shamimjucse	Palindromes (APIO14_palindrome)	C++14	100 / 100	60 ms	34844 KiB

palindrome

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

const int mx = 300005;
struct Node
{
    int len,link,next[26];
};
string s;
Node tr[mx];
int node; /// node 1 - root with len -1, node 2 - root with len 0
int suff; /// max suffix palindrome
inline int New()
{
    node++;
    tr[node].len = 0, tr[node].link = 0;
    memset(tr[node].next, 0, sizeof tr[node].next);
    return node;
}
int cnt[mx];
inline bool Insert(int pos)
{
    int cur = suff, curlen = 0;
    int c = s[pos]-'a'; ///check it
    while(true) ///Finding maximum length palindromic suffix
    {
        curlen = tr[cur].len;
        if (pos-1-curlen>=0 && s[pos-1-curlen]==s[pos])
            break;
        cur = tr[cur].link;
    }
    if(tr[cur].next[c]) ///Existing node
    {
        suff = tr[cur].next[c];
        cnt[suff]++;
        return false;
    }

    suff = New();
    tr[node].len = tr[cur].len + 2;
    tr[cur].next[c] = node;
    if(tr[node].len == 1) ///Single character, connected with root
    {
        tr[node].link = 2;
        cnt[suff]++;
        return true;
    }
    while(true)///Finding suffix link
    {
        cur = tr[cur].link;
        curlen = tr[cur].len;
        if(pos-1-curlen>=0 && s[pos-1-curlen]==s[pos])
        {
            tr[node].link = tr[cur].next[c];
            break;
        }
    }
    cnt[suff]++;
    return true;
}
void initTree()
{
    node = 2, suff = 2;
    tr[1].len = -1, tr[1].link = 1;
    tr[2].len = 0, tr[2].link = 1;
    memset(tr[1].next,0,sizeof tr[1].next);
    memset(tr[2].next,0,sizeof tr[2].next);
}
void buildTree()
{
    initTree();
    for(int i=0;i<s.size();i++)
    {
        Insert(i);
        //cnt[tr[suff].link]+=cnt[suff];
    }
}
long long sm = 0;
void count()
{
    for(int i=node;i>2;i--)
    {
        cnt[tr[i].link]+=cnt[i];
        sm = max(sm,1LL*cnt[i]*tr[i].len);
    }
}
int main()
{
    cin >> s;
    buildTree();
    count();
    cout << sm << endl;
    return 0;
}

Compilation message (stderr)

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

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