Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Re: longest common substring (with needed tweaks)

by oiskuu (Hermit)
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:

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (5)
As of 2018-01-19 18:32 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (222 votes). Check out past polls.