#!/usr/bin/perl

my $NICE_Q = 8355967;

# rabin_karp_sum( $S, $q, $n )
#
# $S is the string to be summed
# $q is the modulo base (default $NICE_Q)
# $n is the (prefix) length of the string to summed (default length($S))

sub rabin_karp_sum_modulo_q {
    my ( $S ) = shift; # The string.

    use integer; # We use only integers.

    my $q = @_ ? shift : $NICE_Q;
    my $n = @_ ? shift : length( $S );

    my $Sigma = 256; # Assume 8-bit text.

    my ( $i, $sum, $hipow );

    if ( @_ ) { # Incremental summing.
        ( $i, $sum, $hipow ) = @_;

        if ($i > 0) {
            my $hiterm; # The contribution of the highest digit.

            $hiterm  = $hipow * ord( substr( $S, $i - 1, 1 ) );
            $hiterm %= $q;
            $sum -= $hiterm;
        }

        $sum *= $Sigma;
        $sum += ord( substr( $S, $n + $i - 1, 1 ) );
        $sum %= $q;

        return $sum; # The sum.
    } else {            # Total summing.
        ( $sum, $hipow ) = ( ord( substr( $S, 0, 1 ) ), 1 );

        for ( $i = 1; $i < $n; $i++ ) {
            $sum *= $Sigma;
            $sum += ord( substr( $S, $i, 1 ) );
            $sum %= $q;

            $hipow *= $Sigma;
            $hipow %= $q;
        }

        # Note that in array context we return also the highest used
        # multiplier mod $q of the digits as $hipow,
        # e.g., 256**4 mod $q == 3599 for $n == 5.

        return wantarray ? ( $sum, $hipow ) : $sum;
    }
}

sub rabin_karp_modulo_q {
    my ( $T, $P, $q ) = @_; # The string, pattern, and optional modulo.

    use integer;

    my $n = length( $T );
    my $m = length( $P );

    return -1 if $m  > $n;
    return  0 if $m == $n and $P eq $T;

    $q = $NICE_Q unless defined $q;

    my ( $KRsum_P, $hipow ) = rabin_karp_sum_modulo_q( $P, $q, $m );
    my ( $KRsum_T )         = rabin_karp_sum_modulo_q( $T, $q, $m );

    return 0 if $KRsum_T == $KRsum_P and substr( $T, 0, $m ) eq $P;

    my $i;
    my $last_i = $n - $m; # $i will go from 1 to $last_i.

    for ( $i = 1; $i <= $last_i; $i++ ) {

        $KRsum_T =
            rabin_karp_sum_modulo_q( $T, $q, $m, $i, $KRsum_T, $hipow );

        return $i
            if $KRsum_T == $KRsum_P and substr( $T, $i, $m ) eq $P;
    }

    return -1; # Mismatch.
}