Count occurrences of a substring: Difference between revisions
Added Quackery.
m (Updated description and link for Fōrmulæ solution) |
(Added Quackery.) |
||
Line 2,464:
>>> "ababababab".count("abab")
2</lang>
=={{header|Quackery}}==
Quackery does not come equipped with a "find substring m within string n" function, but one is defined in The Book of Quackery, as a demonstration of creating a finite state machine in Quackery. It is reproduced here with permission.
<lang Quackery> [ [] 95 times
[ i^ space +
join ] ] constant is alphabet ( --> $ )
[ [ 2dup != while
-1 split drop
swap 1 split
unrot drop again ]
drop size ] is overlap ( [ [ --> n )
[ temp put [] swap
alphabet witheach
[ over -1 poke
over overlap
dup temp share
= if negate
swap dip join ]
drop temp release ] is eachend ( [ n --> [ )
[ [] swap
dup temp put
size times
[ temp share
i 1+ split drop
temp share size eachend
nested swap join ]
temp release ] is buildfsm ( $ --> [ )
[ dup [] = iff -1
else
[ behead
dup carriage = if
[ drop space ]
space - ]
swap ] is nextcharn ( $ --> n $ )
[ swap dup size
swap temp put
swap 0
[ over swap peek
temp take
nextcharn
temp put
dup 0 < iff
[ 2drop 0 ] done
peek
dup 0 < until ]
nip
temp take size - + ] is usefsm ( $ [ --> n )
[ over size 0 = iff
[ 2drop 0 ]
else
[ swap buildfsm
usefsm ] ] is find$ ( $ $ --> n )</lang>
<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 list of positions of m within n. (It actually returns the position 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.)
<lang Quackery> [ over size 0 = iff
[ 2drop [] ] done
[] unrot
swap buildfsm
[ 2dup usefsm
rot 2dup found while
dip [ over size + ]
dip
[ rot over join
unrot ]
swap split
nip swap again ]
2drop drop ] is findall$ ( $ $ --> [ )
</lang>
{{out}}
Testing <code>findall$</code> in the Quackery shell.
<pre>O> $ "th" $ "the three truths" tuck findall$
... witheach [ split swap echo$ cr ]
... echo$
...
th
e th
ree truth
s
Stack empty.
</pre>
Finally we cal use <code>findall$</code> to fulfil the task requirements.
<lang Quackery> [ swap findall$ size ] is occurences ( $ $ --> n )
$ "the three truths" $ "th" occurences echo cr
$ "ababababab" $ "abab" occurences echo cr
</lang>
{{out}}
<pre>3
2
</pre>
=={{header|R}}==
| |||