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

Re: longest common substring (with needed tweaks)

by oiskuu (Friar)
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 musing on the Monastery: (10)
As of 2015-07-06 07:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (70 votes), past polls