Submission #635789

#	Time	Username	Problem	Language	Result	Execution time	Memory
635789		chonka	Palindromes (APIO14_palindrome)	C++17	0 / 100	35 ms	30480 KiB

palindrome

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int n ;
string a ;

struct node {
    int len , cnt ;
    int to[ 26 ] ;
    int suff ;
    node ( ) {
        len = cnt = suff = 0 ;
        for ( int i = 0 ; i < 26 ; ++ i ) {
            to[ i ] = 0 ;
        }
    }
};

vector < node > v ;

void solve ( ) {
    cin >> a ;
    n = a.size ( ) ;
    v.push_back ( node ( ) ) ;
    v[ 0 ].len = -1 ;
    v.push_back ( node ( ) ) ;

    int wh = 0 ; 
    for ( int i = 0 ; i < n ; ++ i ) {
        while ( wh > 0 && ( i - v[ wh ].len - 1 < 0 || a[ i - v[ wh ].len - 1 ] != a[ i ] ) ) {
            wh = v[ wh ].suff ;
        }
        if ( v[ wh ].to[ ( a[ i ] - 'a' ) ] == 0 ) {
            v.push_back ( node ( ) ) ;
            v[ wh ].to[ ( a[ i ] - 'a' ) ] = (int)v.size ( ) - 1 ;
            v.back ( ).len = v[ wh ].len + 2 ;
            int dummy = v[ wh ].suff ;
            while ( dummy > 0 && ( i - v[ dummy ].len - 1 < 0 || a[ i - v[ dummy ].len - 1 ] != a[ i ] ) ) {
                dummy = v[ dummy ].suff ;
            }
            v[ wh ].suff = v[ dummy ].to[ ( a[ i ] - 'a' ) ] ;
        }
        wh = v[ wh ].to[ ( a[ i ] - 'a' ) ] ;        
        ++ v[ wh ].cnt ;
    }
    ll ans = 0 ;
    int sz = v.size ( ) ;
    for ( int i = sz - 1 ; i >= 0 ; -- i ) {
        v[ v[ i ].suff ].cnt += v[ i ].cnt ;
        ans = max ( ans , 1LL * v[ i ].len * v[ i ].cnt ) ;
    }
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

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