Submission #635790

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

palindrome

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

const int MAXN = 4e5 + 7 ;

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 ;
        }
    }
};
node v[ MAXN ] ;


void solve ( ) {
    cin >> a ;
    n = a.size ( ) ;
    v[ 0 ].len = -1 ;
    int tp = 1 ;
    
    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[ wh ].to[ ( a[ i ] - 'a' ) ] = ++ tp ;
            v[ tp ].len = v[ wh ].len + 2 ;
            if ( v[ tp ].len > 1 ) { 
                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[ tp ].suff = v[ dummy ].to[ ( a[ i ] - 'a' ) ] ;
            }
            else {
                v[ tp ].suff = 1 ;
            }
        }
        wh = v[ wh ].to[ ( a[ i ] - 'a' ) ] ;        
        ++ v[ wh ].cnt ;
    }
    ll ans = 0 ;
    for ( int i = tp ; 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: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27