Submission #1319389

#TimeUsernameProblemLanguageResultExecution timeMemory
1319389NValchanovPalindromes (APIO14_palindrome)C++20
100 / 100
48 ms62888 KiB
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long llong;

const int MAXN = 3e5 + 10;
const int ALPHA = 26;

struct PalindromicTree
{
    int n, last, sz;
    llong ans;

    struct Node
    {
        int len, sufflink, cnt;
        int nxt[ALPHA];
        vector < int > adj;

        Node(){};
    };

    char str[MAXN];
    Node tree[MAXN];

    PalindromicTree(){};

    void init()
    {
        str[0] = -1;

        tree[0].sufflink = 1;
        tree[0].len = 0;
        tree[1].sufflink = 1;
        tree[1].len = -1;

        sz = 2;
        n = 0;
        last = 1;
    }

    int get_par(int u)
    {
        
        while(str[n - tree[u].len - 1] != str[n])
        {

            u = tree[u].sufflink;
        }

        return u;
    }

    void update(char c)
    { 
        str[++n] = c;

        int letter = c - 'a';

        int par = get_par(last);

        if(!tree[par].nxt[letter])
        {
            int suff = get_par(tree[par].sufflink);

            tree[sz].len = tree[par].len + 2;
            tree[sz].sufflink = tree[suff].nxt[letter];

            tree[sz].cnt = 1;
            tree[par].nxt[letter] = sz;
            tree[tree[sz].sufflink].adj.push_back(sz);

            sz++;
        }
        else
        {
            tree[tree[par].nxt[letter]].cnt++;
        }

        last = tree[par].nxt[letter];
    }

    void build(string s)
    {
        for(int i = 0; i < s.size(); i++)
        {
            update(s[i]);
        }
    }

    void dfs(int u)
    {
        for(int v : tree[u].adj)
        {
            dfs(v);

            tree[u].cnt += tree[v].cnt;
        }

        ans = max(ans, 1LL * tree[u].cnt * tree[u].len);
    }
};

PalindromicTree paltree;

string s;

int main()
{
    cin >> s;

    paltree.init();
    paltree.build(s);
    paltree.dfs(0);

    cout << paltree.ans << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...