Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: Pattern Searching

by grondilu (Friar)
on Nov 10, 2012 at 12:18 UTC ( #1003253=note: print w/replies, xml ) Need Help??

in reply to Pattern Searching

Common pattern in different strings? Using KMP?

I think I solved the corresponding problem on Here is my solution:

#!/usr/bin/perl use strict; use warnings; sub kmp { my @T = (-1, 0); my ($pos, $cnd) = (2, 0); while ( $pos <= @_ ) { if ($_[$pos-1] eq $_[$cnd]) { $T[$pos++] = ++$cnd } elsif ($cnd > 0) { $cnd = $T[$cnd] // 0 } else { $T[$pos++] = 0 } } shift @T; return @T; } use List::Util qw(max min); sub lcs { my @first = split //, my $first = shift; my $n = @first; my @string = map [ split //, $_ ], @_; my ($pos, $length) = (0, 0); SUFFIX: for my $p ( 0 .. $n - 1 ) { shift @first if $p; my @max; for (@string) { my @kmp = kmp @first, '$', @$_; my $max = max @kmp; next SUFFIX if $max < $length; push @max, $max; } if ((my $min = min @max) > $length) { ($pos, $length) = ($p, $min); } } return substr $first, $pos, $length; } open my $f, '< rosalind_lcs.txt' or die "could not open: $!"; say lcs <$f>;

Hope this will help

Replies are listed 'Best First'.
Re^2: Pattern Searching
by Anonymous Monk on Nov 10, 2012 at 17:31 UTC

    hey Monkeys I need more support. I am trying this from 10 hours. I have to show results to my supervisor. I try my level best and still trying. The problem is in printing the @loc array in 2nd iteration. I try my level best to debug this. What I understand is that in 2nd iteration the condition is true for only one time where as the @loc array values shows that the condition should be true for all values.I tried to fix it but all results into nothing. Please help me.

      sorry the word is PerlMonks not monkeys. Extremely sorry.
        Where do you work? Who is your supervisor?

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1003253]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2018-05-28 02:34 GMT
Find Nodes?
    Voting Booth?