Submission #843834

#	Time	Username	Problem	Language	Result	Execution time	Memory
843834		arnold518	Palindromes (APIO14_palindrome)	C++17	0 / 100	35 ms	45856 KiB

palindrome

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N;
string S;

struct Node
{
    int len, link;
    vector<int> chd;
    Node()
    {
        len=0; link=-1;
        chd=vector<int>(26, -1);
    }
};

Node NS[MAXN+10];
int ncnt, P[MAXN+10];

int newNode()
{
    return ncnt++;
}

void EERTREE(int N, string S)
{
    int root1=newNode(), root2=newNode(); // root1 : -1, root2 : 0
    NS[root1].len=-1; NS[root1].link=root1;
    NS[root2].len=0; NS[root2].link=root1;
    int cur=root1;

    for(int i=1; i<=N; i++)
    {
        int v;
        for(v=cur; v!=root1 && S[i-NS[v].len-1]!=S[i]; v=NS[v].link);
        if(NS[v].chd[S[i]-'a']!=-1) cur=NS[v].chd[S[i]-'a'];
        else
        {
            cur=NS[v].chd[S[i]-'a']=newNode();
            NS[cur].len=NS[v].len+2;
            
            for(v=NS[v].link; v!=root1 && S[i-NS[v].len-1]!=S[i]; v=NS[v].link);
            if(v==root1) NS[cur].link=root2;
            else NS[cur].link=NS[v].chd[S[i]-'a'];
        }
        P[i]=cur;
    }
}

int dp[MAXN+10];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin>>S;
    N=S.size();
    S="?"+S;

    EERTREE(N, S);
    for(int i=1; i<=N; i++) dp[P[i]]++;
    ll ans=0;
    for(int i=ncnt-1; i>=0; i--)
    {
        ans=max(ans, (ll)dp[i]*NS[i].len);
        dp[NS[i].link]+=dp[i];
    }
    printf("%lld\n", ans);
}

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