Submission #313178

#	Time	Username	Problem	Language	Result	Execution time	Memory
313178		vipghn2003	Palindromes (APIO14_palindrome)	C++14	100 / 100	108 ms	108928 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

const int N=3e5+5;
struct Node
{
    int nxt[26],sufflink;
    int len,cnt;
    vector<int>edges;
} tree[N*2];

string s;
int suff, num;
long long ans=0;

void add_letter(int pos)
{
    int curr=suff;
    int curr_len=0;
    int letter=s[pos]-'a';
    while(true)
    {
        curr_len=tree[curr].len;
        if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos]) break;
        curr=tree[curr].sufflink;
    }
    if(tree[curr].nxt[letter])
    {
        suff=tree[curr].nxt[letter];
        tree[suff].cnt++;
        return;
    }
    suff=++num;
    tree[num].len=tree[curr].len+2;
    tree[num].cnt=1;
    tree[curr].nxt[letter]=num;
    if(tree[num].len==1)
    {
        tree[num].sufflink=2;
        tree[2].edges.push_back(num);
        return;
    }
    while(true)
    {
        curr=tree[curr].sufflink;
        curr_len=tree[curr].len;
        if(pos-1-curr_len>=0&&s[pos-1-curr_len]==s[pos])
        {
            tree[num].sufflink=tree[curr].nxt[letter];
            tree[tree[curr].nxt[letter]].edges.push_back(num);
            break;
        }
    }
}

void init()
{
    num=2;
    suff=2;
    tree[1].len=-1;
    tree[1].sufflink=1;
    tree[2].len=0;
    tree[2].sufflink=1;
    tree[1].edges.push_back(2);
}

void dfs(int node=1)
{
    for(auto&i:tree[node].edges)
    {
        dfs(i);
        tree[node].cnt+=tree[i].cnt;
    }
    ans=max(ans,1ll*tree[node].len*tree[node].cnt);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    init();
    for(int i=0;i<s.size();i++) add_letter(i);
    dfs();
    cout<<ans;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<s.size();i++) add_letter(i);
      |                 ~^~~~~~~~~

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