#!/usr/bin/perl

sub knuth_morris_pratt_next {
    my ( $P ) = @_; # The pattern.

    use integer;

    my ($m, $i, $j ) = ( length $P, 0, -1 );
    my @next;

    for ($next[0] = -1; $i < $m; ) {
        # Note that this while() is skipped during the first for() pass.
        while ( $j > -1 &&
                substr( $P, $i, 1 ) ne substr( $P, $j, 1 ) ) {
            $j = $next[ $j ];
        }
        $i++;
        $j++;
        $next[ $i ] =
            substr( $P, $j, 1 ) eq substr( $P, $i, 1 ) ?
                $next[ $j ] : $j;
     }

    return ( $m, @next ); # Length of pattern and prefix function.
}

sub knuth_morris_pratt {
    my ( $T, $P ) = @_; # Text and pattern.

    use integer;

    my $m = knuth_morris_pratt_next( $P );
    my ( $n, $i, $j ) = ( length($T), 0, 0 );
    my @next;

    while ( $i < $n ) {
        while ( $j > -1 &&
                substr( $P, $j, 1 ) ne substr( $T, $i, 1 ) ) {
            $j = $next[ $j ];
        }
        $i++;
        $j++;
        return $i - $j if $j >= $m; # Match.
    }

    return -1; # Mismatch.
}