Count occurrences of a substring: Difference between revisions
Content deleted Content added
No edit summary |
|||
Line 2,324:
echo substr_count("ababababab", "abab"), PHP_EOL; // prints "2"
</lang>
=={{header|Picat}}==
Picat has a predicate for searching for substrings (find/4) but on backtracking (e.g. in a findall/2 wrapper) it yields all overlapping substrings which is not correct in this task.
So we have to roll our own. Here are two versions:
* count_substrings_rec/2: Uses recursion ("Prolog style")
* count_substrings_find: Iterative version: Uses find/4 in a while loop.
The time differences between these two versions are quite large which is shown in this benchmark of searching the substring "ab" in a string of 100 000 random characters from the set of "abcde":
* count_substrings_rec/2: 0.009s
* count_substrings_find: 0.501s
<lang Picat>% Recursive version
count_substrings_rec(S, SB) = C =>
count_rec(S,SB,0,C).
count_rec([],_SB,Count,Count).
count_rec(SBRest,SB,Count0,Count) :-
SBRest = SB ++ Rest, % "split" into substring and the rest of the string
count_rec(Rest,SB,Count0+1,Count).
count_rec([T|Rest],SB,Count0,Count) :-
T != SB, % this character is not a substring
count_rec(Rest,SB,Count0,Count).
% Iterative version using find/4 (wrap with once/1 to avoid backtracking).
% (Inspired by the Euphoria version.)
count_substrings_it_find(S, SB) = C =>
SLen = S.len,
Count = 0,
From = 1,
while (From <= SLen)
(
once(find(slice(S,From),SB,_From2,To)) ->
Count := Count + 1,
From := From + To
;
From := From + 1
)
end,
C = Count.</lang>
=={{header|PicoLisp}}==
|