#!/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;}