use strict;
use warnings;
use feature 'say';
use Config;
use Benchmark 'cmpthese';

say "$^V / $Config{ archname } / $Config{ gccversion }";

my $L = 1e5;
my $s = '(' x $L;
my @samples;

for ( 0 ... 99 ) {
    my $s1 = $s;
    for ( 0 .. $L - 1 ) {
        substr $s1, $_, 1, ')' if int rand 2
    }
    push @samples, $s1;
    die unless longest_p_pwc( $s1 ) ==
               longest_p_sum( $s1 )
}

cmpthese -3, {
    pwc => sub { longest_p_pwc( $_ ) for @samples },
    sum => sub { longest_p_sum( $_ ) for @samples },
};

sub valid_longest_parenthesis {
    my $s       = shift;
    my @stack   = (-1);
    my $max_len = 0;

    for my $i (0 .. length($s) - 1) {
        if (substr($s, $i, 1) eq "(") {
            push @stack, $i;
        } else {
            pop @stack;
            if (@stack) {
                $max_len = $max_len > ($i - $stack[-1])
                          ? $max_len : ($i - $stack[-1]);
            } else {
                push @stack, $i;  # New starting point
            }
        }
    }

    return $max_len;
}

use Inline C => << 'END_OF_C';

int longest_p_pwc( SV* str ) {
    STRLEN len;
    char* buf = SvPVbyte( str, len );
    
    int* stack = malloc( len * sizeof( int ));
    int stack_i = 0;
    stack[ 0 ] = -1;

    int max = 0;
    for ( int i = 0; i < len; i ++ ) {
        if ( buf[ i ] == '(' ) stack[ ++ stack_i ] = i;
        else {
            if ( stack_i > 0 ) {
                stack_i --;
                int cur = i - stack[ stack_i ];
                if ( cur > max ) max = cur;
            }
            else stack[ 0 ] = i;
        }
    }
    free( stack );
    
    return max;
}

int longest_p_sum( SV* str ) {
    STRLEN len;
    char* buf = SvPVbyte( str, len );
   
    int* pad = malloc( len * sizeof( int ));
    int sum = 0;
    for ( int i = 0; i < len; i ++ ) 
        pad[ i ] = sum = 
            sum + !sum + ( buf[ i ] == '(' ? 1 : -1 );
    int max = 0;
    int cur = 0;
    int counting = 0;
    int zeroless = 1;
    sum = 0;
    for ( int i = len - 1; i >= 0; i -- ) {
        zeroless = zeroless && pad[ i ];
        sum = zeroless 
            ? sum + !sum + ( buf[ i ] == ')' ? 1 : -1 ) 
            : 1;
        if ( pad[ i ] && sum ) {
            cur ++;
            counting = 1;
        }
        else if ( counting ) {
            if ( cur > max ) max = cur;
            counting = 0;
            cur = 0;
        }
    }
    if ( cur > max ) max = cur;
    free( pad );
    
    return max;
}

END_OF_C