Count occurrences of a substring: Difference between revisions

<code>find$</code> builds a finite state machine to search for m, (an O(m³) operation), then uses it to search in n with O(n). Rather than use <code>find$</code>, and repeatedly build the same fsm, we will define a word <code>findall$</code> which returns a nest (i.e. list) of positions of m within n. (It actually returns the positionpositions of the end of the substring, relative to (for the first instance) the start of the string, or (for subsequent instances) the end of the previous instance of the substring.)