title: Knuth Morris Pratt Algorithm implementation in Perl
body: <p>I am trying to implement the <a href="https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" rel="nofollow">Knuth Morris Pratt algorithm</a> in Perl. The following is my code and I referred Mastering Algorithms in Perl First Edition for the algorithm. When I run the code, it prints -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 as a result. Where am I going wrong?</p>
  
  <p>Code:</p>
  
  <pre><code>#!/usr/local/bin/perl
  
  #text
  my $seq = "babacbadbbac";
  
  #pattern
  my $motif = "acabad";
  
  #pass the text and pattern to knuth_morris_pratt subroutine
  my @res = knuth_morris_pratt($seq, $motif);
  
  #print the result
  print "The resulting array is:";
  print "@res";
  
  #computation of the prefix subroutine
  sub knuth_morris_pratt_next
  {
     my($P) = @_; #pattern
     use integer;
     my ( $m, $i, $j ) = ( length $P, 0, -1 );
     my @next;
     for ($next[0] = -1; $i &lt; $m; ) {
        # Note that this while() is skipped during the first for() pass.
        while ( $j &gt; -1 &amp;&amp; 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.
  }
  
  #matcher subroutine
  sub knuth_morris_pratt
  {
     my ( $T, $P ) = @_; # Text and pattern.
     use integer;
     my ($m,@next) = knuth_morris_pratt_next( $P );
     my ( $n, $i, $j ) = ( length($T), 0, 0 );
     #my @next;
     my @val;
     my $k=0;
     while ( $i &lt; $n ) 
     {
        while ( $j &gt; -1 &amp;&amp; substr( $P, $j, 1 ) ne substr( $T, $i, 1 ) ) 
        {
           $j = $next[$j];
        }
        $i++;
        $j++;
        if($j&gt;=$m)
        {
            $val[$k]= $i - $j; # Match.
        }
        else
        {
            $val[$k]=-1; # Mismatch.
        }
        $k++;
     }
     return @val; 
  }
  </code></pre>