Do you know where your variables are? PerlMonks

 on Oct 08, 2013 at 12:57 UTC ( #1057416=scratchpad: print w/ replies, xml ) Need Help??

#### 100% Attitude

1. ```use bigint;
use List::Util qw(sum);
{ my @M = ((0)x99, 1); sub NUM { \$M[99+\$_[0]] //= sum map NUM(\$_+\$_[0]
+), -26..-1 } }
print NUM(100);
2. ```use bigint;
my @M = (1);
for my \$i (0..99) { \$M[\$i+\$_] += \$M[\$i] for 1..26 }
print \$M[100];

#### For R56, Re: longest common substring (with needed tweaks)

```sub cpfx { (\$_[0]^\$_[1]) =~ /^\0*/; substr(\$_[0], 0, \$+[0]) }
sub sufs { map {[substr(\$_[0], -\$_) => \$_[1]]} 1..length(\$_[0]) }
my @SA = sort {\$a->[0] cmp \$b->[0]} map {sufs(\$dta[\$_], \$_)} 0..\$#dta;
The cpfx() returns longest common prefix of two string arguments; sufs() returns a list of all suffixes of a string, bundled with an ID. The @SA contains all suffixes of all strings in a sorted order. It is essentially a suffix array. Size of @SA equals the total number of characters in all strings. Note that this sort is the slowest part of the search. Clever algorithms can do this much more efficiently than a generic sort.
```my @N = (0) x @dta;
my (\$best, \$n, \$h, \$t) = ("", 0, 0, 0);
The \$h and \$t are head and tail index of a sliding window over @SA. Since @SA is sorted, the longest common prefix substring will be found among (tail, head) pairs of suffixes. Now it remains to iterate over @SA, all the while keeping the window such that it spans over \$nmin different string ID's.
```while (\$h < @SA) {
(\$n += !\$N[\$SA[\$h++]->[1]]++) >= \$nmin or next;
(\$n -= !--\$N[\$SA[\$t++]->[1]]) while \$n > \$nmin || \$N[\$SA[\$t]->[1]] >
+ 1;
my \$pfx = cpfx(\$SA[\$t]->[0], \$SA[\$h-1]->[0]);
\$best = \$pfx if length(\$best) < length(\$pfx);
}
Here, \$n tracks the number of different input strings that the window covers; @N keeps the counts of ID's in the window. Whenever \$N[...] is adjusted from/to zero, the \$n changes. The inner while ensures minimum possible window.

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (17)
As of 2013-12-06 22:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?