R. Clayton (rclayton@monmouth.edu)
(no date)
For completeness, here's the array-recursive implementation of star runs:
static unsigned
star_run_size(const char * const str, unsigned i, unsigned n) {
// Return the length of the star run starting at str[i].
unsigned cnt = 0;
if (i >= 0)
while ((i < n) and ('*' == str[i++]))
cnt++;
return cnt;
}
static int
left_longest_star_run(const char * const str, unsigned i, unsigned n) {
// Return the index of the leftmost longest run of stars in str[i..n-1]
// or -1 if there's no such run.
// The empty string.
if (i >= n)
return -1;
// The rest of the string.
const int llsr = left_longest_star_run(str, i + 1, n);
// The element.
const unsigned srs = star_run_size(str, i, n);
if ((srs > 0) and (srs >= star_run_size(str, llsr, n)))
return i;
else
return llsr;
}
You may be asking yourself "If array-recursive algorithms are so great, why
didn't you write star_run_size() that way?" An excellent observation; I'll
leave it to you rewrite star_run_size() as an array-recursive algorithm. See
the lecture notes for full details.
This archive was generated by hypermail 2.0b3 on Mon Dec 15 2003 - 19:45:05 EST