CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner:
Knuth Morris Pratt

 



Duril
New User

Dec 29, 2011, 4:59 AM

Post #1 of 1 (483 views)
Knuth Morris Pratt Can't Post

Hello,

I would like the Knuth - Morris - Pratt algorithm implemented in Perl and have it already written two subs. The prefix sub and sub match.

Now I do not know if this is so accurate? The syntax is okay. But as I get the program to run and talk to the subs, it is possible to read a lot of data? All this would be a test for sequencing and I will want to test it a lot on the basis of appropriate data from the lab. But unfortunately, my knowledge of Perl is not so good.

I would be grateful for any help,

lg Duril

The code:




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

# Prefix

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

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); # lenght off pattern und der Prefix function
}



# Matcher


sub ermorde_Knuth { #knuth_morris_pratt Subroutine
my ( $T, $P ) = @_; # text und pattern.

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
}
return -1;} # Mismatch


 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives