/*

  Count occurrences of a substring in Picat.

  From
  http://rosettacode.org/wiki/Count_occurrences_of_a_substring
  """
  The task is to either create a function, or show a built-in function, 
  to count the number of non-overlapping occurrences of a substring 
  inside a string. The function should take two arguments: the first 
  argument being the string to search and the second a substring to be 
  search for. It should return an integer count.
  
  print countSubstring("the three truths","th")
  3

  //  do not count substrings that overlap with previously-counted substrings:
  print countSubstring("ababababab","abab")
  2

  The matching should yield the highest number of non-overlapping matches. 
  In general, this essentially means matching from left-to-right or 
  right-to-left (see proof on talk page).
  """

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.

main => go.

go =>
   println(count_substrings("the three truths", "th")), % 3
   println(count_substrings("ababababab", "abab")),     % 2
   println(count_substrings("aaaaaaaaaaa", "aa")),      % 5
   println(count_substrings("aaaaaaaaaaa", "c")),       % 0
   nl.

% Wrong
go2 =>
   println("This is not correct but is included anyway...."),
   println(count_substrings2("the three truths", "th")), % 3
   println(count_substrings2("ababababab", "abab")),     % 2
   println(count_substrings2("aaaaaaaaaaa", "aa")),      % 5
   println(count_substrings2("aaaaaaaaaaa", "c")),       % 0
   nl.

% Wrong
go3 =>
   println(count_substrings3("the three truths", "th")), % 3
   println(count_substrings3("ababababab", "abab")),     % 2
   println(count_substrings3("aaaaaaaaaaa", "aa")),      % 5
   println(count_substrings3("aaaaaaaaaaa", "c")),       % 0
   nl.

% Nope
go4 =>
   println(count_substrings4("the three truths", "th")), % 3
   println(count_substrings4("ababababab", "abab")),     % 2
   println(count_substrings4("aaaaaaaaaaa", "aa")),      % 5
   println(count_substrings4("aaaaaaaaaaa", "c")),       % 0
   nl.


go5 =>
   println(count_substrings5("the three truths", "th")), % 3
   println(count_substrings5("ababababab", "abab")),     % 2
   println(count_substrings5("aaaaaaaaaaa", "aa")),      % 5
   println(count_substrings5("aaaaaaaaaaa", "c")),       % 0
   nl.


count_substrings(S, SB) = C =>
   C1 = 0,
   I = 1,
   SLen = S.length,
   SBLen = SB.length,
   while (I < SLen, I+SBLen <= SLen)
     SS = [S[J] : J in I..I+SBLen-1],
     if SS == SB then
        C1 := C1 +1,
        I := I + SBLen
     else
        I := I+1
     end
   end,
   C = C1.


% Note: This use the built-in (and non-deterministric) predicate
%       find/4.
%       However, this is not correct - according to the specification of the
%       problem - since it count _all_ occurences, including all overlapping 
%       substrings.
%       It is included just for show.
%
count_substrings2(S, SB) = C => 
    L = findall([From,To], find(S,SB,From,To)),
    println(L),
    C = L.length.

% Same result as count_substrings2, i.e. not correct
count_substrings3(S, SB) = C => 
    L = findall(SB, append(_,SB,_,S)),
    println(L),
    C = L.length.

% Nope.
count_substrings4(S, SB) = C => 
    count_substrings_dcg(L,S,SB,Rest),
    println([l=L,sb=SB,s=S,rest=Rest]),
    println(L),
    C = L.length.

count_substrings5(S, SB) = C => 
    % count_select(S,SB,0,C).
    count_select(S,SB,C).


% count_select([],_SB,Count,Count).
% count_select(SSB,SB,Count0,Count) :-
%   SSB = SB ++ Rest,
%   count_select(Rest,SB,Count0+1,Count).

% count_select([T|Rest],SB,Count0,Count) :-
%   T != SB,
%   count_select(Rest,SB,Count0,Count).


count_select([],_SB,0).
count_select(SSB,SB,Count0,Count) :-
  SSB = SB ++ Rest,
  count_select(Rest,SB,Count0+1,Count).

count_select([T|Rest],SB,Count0,Count) :-
  T != SB,
  count_select(Rest,SB,Count0,Count).



% Nope!
any --> [] ; [C], {println(any=C)}, any.
many([C|Cs]) --> [C], {println(many=C)},many(Cs).
count_substrings_dcg1(Sub) --> any,many(Sub), {println(sub=Sub)},any.

count_substrings_dcg([Sub|Ss],Sub) --> count_substrings_dcg1(Sub), count_substrings_dcg(Ss,Sub).
count_substrings_dcg(Sub,Sub) --> count_substrings_dcg1(Sub).
count_substrings_dcg([],_) --> [].