#!/usr/bin/perl -w
use strict;
use warnings;


#   Berechnung des Präfix  ######                                         

sub ermorde_Knuth_next{              
	my($P)=@_;                        # das Muster

	use integer;
	
	my$m=(0..lenght($P)-1); 
	my$i=0;
	my$j=-1;
	
	my @next;                         # Array 


	for ($next[0] = -1; $i < $m; ) {
	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);     # Länge des Musters und der Prefix Funktion
}


##############################################

 						#Matcher                                                

    
	sub ermorde_Knuth  {         
   	 my ( $T, $P ) = @_; 		# Text und Muster.
    
    use integer;
    
    my $m = ermorde_Knuth_next( $P );   #knuth_morris_pratt_next
    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 - Hurra wir haben einen Treffer.
    }
    return -1;}