/* 

  Rep string (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Rep-string
  """
  Given a series of ones and zeroes in a string, define a repeated string or rep-string 
  as a string which is created by repeating a substring of the first N characters of 
  the string truncated on the right to the length of the input string, and in which 
  the substring appears repeated at least twice in the original.

  For example, the string '10011001100' is a rep-string as the leftmost four characters 
  of '1001' are repeated three times and truncated on the right to give 
  the original string.

  Note that the requirement for having the repeat occur two or more times means 
  that the repeating unit is never longer than half the length of the input string.

  The task is to:

    - Write a function/subroutine/method/... that takes a string and returns an indication 
      of if it is a rep-string and the repeated string. (Either the string that is 
      repeated, or the number of repeated characters would suffice).
    - There may be multiple sub-strings that make a string a rep-string - in that case 
      an indication of all, or the longest, or the shortest would suffice.
    - Use the function to indicate the repeating substring if any, in the following: 

      '1001110011'
      '1110111011'
      '0010010010'
      '1010101010'
      '1111111111'
      '0100101101'
      '0100100'
      '101'
      '11'
      '00'
      '1'

    - Show your output on this page. 
  """

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

*/


import util.

main => go.


go => 
  Strings = [
                 "1001110011",       % 10011
                 "1110111011",       % 1110
                 "0010010010",       % 001
                 "1010101010",       % 1010
                 "1111111111",       % 11111
                 "0100101101",       % no solution
                 "0100100",          % 010
                 "101",              % no solution
                 "11",               % 1
                 "00",               % 0
                 "1",                % no solution
                 "",                 % no solution
                 "123123123123123",  % 123123
                 "12312312312312",   % 123123
                 "123123123123124",  % no solution
                 "abcabcdabcabcdabc", % abcabcd
                 [1,2,3,4,1,2,3,4,1,2,3] % 1,2,3,4
                 
            ],
  foreach(S in Strings) 
    printf("%w: ", S),
    if maxrep(S,Substr,N) then
      println([substr=Substr,n=N])
    else
      println("no solution")
    end
  end,
  nl.
 
% the largest repeating substring
maxrep(S,Substr,N) => 
  maxof(rep(S,Substr,N),N).

rep(S,Substr,N) => 
  between(1,S.length div 2, N),
  Len = S.length,
  Len2 = Len - (Len mod N),
  Substr = slice(S,1,N),
  % count the number of proper slices   
  SS = [1 : I in 1..N..Len2, slice(S,I,I+N-1) = Substr],
  SS.length = Len div N,
  % the last (truncated) slice (or []) must be a substring of Substr
  Rest = slice(S,Len2+1,Len),
  find(Substr,Rest,1,_).