I make no claims as to being optimal, but in the theory of "ops are bad,
m'kay" (with a nod to Nick Clark), here's what I did:
perl -le 'my @s; $_ = "greensleeves"; /(.+?)(??{push @s,$1})(?!)/; print "@s"'
It's roughly the same algorithm, since it's inherently O(n^2) to generate
substrings. [For a string of length n, there are n starting positions, and
from each position i, running from 0 to n-1, there are n-i substrings to be
had.] This solution does minimise the real ops in perl by letting the
regexp engine handle the actual finding of the substrings. On the other
hand, the (??{code}) construct has close to eval/sub-entry overhead. I
don't recommend this for readability. Its real value was in minimising my
debugging time.
Done as a subroutine (should anyone care):
sub gen_substrs ($) {
my $str = shift;
my @s;
$str =~ /(.+?)(??{push @s,$1})(?!)/;
@s;
}
For actual enumeration, for a string of length n, the number of non-null
contiguous substrings is:
(n^2 + n) / 2
In particular, for "greensleeves", which is a 12-character string, there are
78 such substrings to be found. Because of the repeated letters in the
starting string, of course, those 78 values are not unique.
Hmm, I had a point when I started. Oh, yeah. As long as your algorithm
isn't of worse complexity than required by the nature of the problem, don't
worry about it too much. Just be sure it gives you the right answers. If
finding the substring lists turns out to be a bottleneck, consider using
Memoize or something similar to avoid re-building the lists for the same
word each time.
Hth,
--s.
--
Spider Boardman (at home) [EMAIL PROTECTED]
The management (my cats) made me say this. http://www.ultranet.com/~spiderb
PGP public key fingerprint: 96 72 D2 C6 E0 92 32 89 F6 B2 C2 A0 1C AB 1F DC
_______________________________________________
Boston-pm mailing list
[EMAIL PROTECTED]
http://mail.pm.org/mailman/listinfo/boston-pm
