#!/usr/bin/perl
use strict;
use warnings;
use interger;


# Allgemein: 
# w /P  = Wort oder Muster (Pattern)
# i = Anfangposition des Suchwortes s im Text t
# j = Position im Suchwort (Länge des Präfixes)
# t  =Text
# n  = Länge des Textes
# s = Suchtwort
# m = Länge des Suchwortes
# s = Suchwort
# m= Länge des Suchwortes 



#        Berechnung der Präfix                                           

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

	my ($m;$i,$j)=(lenght $P,0,-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,@net);     # Länge des Musters und der Prefix Funktion
}


							#Matcher                                                

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