Beefy Boxes and Bandwidth Generously Provided by pair Networks Bob
The stupid question is the question not asked
 
PerlMonks  

Re: longest common substring (with needed tweaks)

by oiskuu (Pilgrim)
on Oct 28, 2013 at 01:56 UTC ( #1059939=note: print w/ replies, xml ) Need Help??


in reply to longest common substring (with needed tweaks)

I'm not entirely sure if I understood the first parameter correctly.
It's just a (redundant) check? No matter.

chomp (my @dta = <DATA>); my ($ntot, $nmin) = split /\s/, shift @dta; die if $nmin < 2 or $nmin > $ntot or $ntot != @dta; sub cpfx { ($_[0]^$_[1]) =~ m/^\0*/s; substr($_[0], 0, length $&) } sub sufs { map {[substr($_[0], -$_) => $_[1]]} 1..length($_[0]) } my @SA = sort {$a->[0] cmp $b->[0]} map {sufs($dta[$_], $_)} 0..$#dta; my @N = (0) x @dta; my ($best, $n, $h, $t) = ("", -$nmin, 0, 0); while ($h < @SA) { ($n += !$N[$SA[$h++]->[1]]++) >= 0 or next; ($n -= !--$N[$SA[$t++]->[1]]) while $n > 0 || $N[$SA[$t]->[1]] > 1; my $pfx = cpfx(map $SA[$_]->[0], $t, $h-1); $best = $pfx if length($best) < length($pfx); } print "\"$best\"\n"; __DATA__ 6 3 You can use the substr() function as an lvalue, in which case EXPR mus +t itself be an lvalue. If you assign something shorter than LENGTH, the string will shrink, and if you assign something longer than LENGTH +, the string will grow to accommodate it. To keep the string the same length, you may need to pad or chop your value using "sprintf". If OFFSET and LENGTH specify a substring that is partly outside the st +ring, only the part within the string is returned. If the substring is beyond either end of the string, substr() returns the undefined val +ue and produces a warning. When used as an lvalue, specifying a substring that is entirely outside the string raises an exception. He +re's an example showing the behavior for boundary cases:


Comment on Re: longest common substring (with needed tweaks)
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2014-04-25 02:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (579 votes), past polls