제출 #843858

#제출 시각아이디문제언어결과실행 시간메모리
843858arnold518Palindromes (APIO14_palindrome)C++17
100 / 100
38 ms46036 KiB
#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
        {
            int par=v;
            cur=newNode();
            
            for(v=NS[v].link; v!=root1 && S[i-NS[v].len-1]!=S[i]; v=NS[v].link);
            if(NS[v].chd[S[i]-'a']==-1) NS[cur].link=root2;
            else NS[cur].link=NS[v].chd[S[i]-'a'];
            
            NS[par].chd[S[i]-'a']=cur;
            NS[cur].len=NS[par].len+2;
        }
        //printf("%d : %d %d\n", cur, NS[cur].len, NS[cur].link);
        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);
}
#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...