Submission #46580

#	Time	Username	Problem	Language	Result	Execution time	Memory
46580		tieunhi	Palindromes (APIO14_palindrome)	C++14	0 / 100	2 ms	352 KiB

palindrome

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 2000005
#define maxc 1000000007

using namespace std;

string s;
int sz, cur;

struct PTNode
{
    int first, length, occurance, suffix, child[26];
    PTNode(int first = 0, int length = 0) : first(first), length(length)
    {
        occurance = suffix = 0;
        for (int i = 0; i < 26; i++) child[i] = 0;
    }
}node[N];

void add(int pos)
{
    int start;
    while (1)
    {
        start = pos - node[cur].length - 1;
        if (start >= 0 && s[start] == s[pos])
            break;
        cur = node[cur].suffix;
    }

    int z = s[pos] - 'a';
    if (node[cur].child[z])
    {
        cur = node[cur].child[z];
        node[cur].occurance++;
        return;
    }

    node[++sz] = PTNode(start, node[cur].length + 2);
    node[cur].child[z] = sz;
    if (node[sz].length == 1)
        node[sz].suffix = 2;
    else
    {
        while (1)
        {
            cur = node[cur].suffix;
            int start = pos - node[cur].length - 1;
            if (start >= 0 && s[start] == s[pos])
                break;
        }
        node[sz].suffix = node[cur].child[z];
    }
    node[sz].occurance++;
    cur = sz;
    return;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> s;
    sz = cur = 2;
    node[1] = PTNode(0, -1); node[2] = PTNode(0, 0);
    node[1].suffix = node[2].suffix = 1;
    for (int i = 0; i < s.size(); i++)
        add(i);
    long long res = 0;
    for (int i = sz; i >= 3; i--)
    {
        node[node[i].suffix].occurance += node[i].occurance;
        res = max(res, 1ll*node[i].occurance*node[i].length);
    }
    cout <<res;
}

Compilation message (stderr)

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

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