Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Pattern Searching

by grondilu (Pilgrim)
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 rosalind.info. 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


Comment on Re: Pattern Searching
Download Code
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?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1003253]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (12)
As of 2014-07-25 15:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (172 votes), past polls