P is for Practical PerlMonks

### Re: Pattern Searching

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

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

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?

Create A New User
Node Status?
node history
Node Type: note [id://1003253]
help
Chatterbox?
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
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (199 votes). Check out past polls.

Notices?