##
## Find the substring in a string.
##
def find_sub(str, subs)
  ## This algorithm runs in O(n) time,
  ## where n is the length of the string.
  ##
  ## Breaking it (for the worst case):
  ## First loop runs for n/m, second loop for n/m*(3m)
  ## which makes it: 2*n/m*3m => 6n => n

  r = -1

  ## Part the string in lengths equal to length of the substring (the last part will be equal/smaller)
  i = 0
  j = subs.length-1
  parts = []
  while true
    parts << [str[i..j], i] unless str[i..j].empty?
    break if str[i..j].length < subs.length
    i = j+1
    j += subs.length
  end
  p parts

  pref = ""
  parts.each do |part|
    if part[0] == subs
      ## found it!
      r = part[1]
      break
    end

    if pref.length > 0
      ## found prefix, match suffix
      prefl = pref.length
      for i in 0..part[0].length-1
        c = part[0][i]
        if subs[i+prefl] == c
          pref.concat(c)
        end
      end
      break if subs == pref
      if prefl == pref.length
        pref = ""
        r = -1
        ## find prefix, in this part
        res = find_prefix(subs, part[0], part[1], pref, r)
        pref, r = res[0], res[1]
      end
    else
      ## find prefix
      res = find_prefix(subs, part[0], part[1], pref, r)
      pref, r = res[0], res[1]
    end
  end
  r
end

def find_prefix(subs, pa0, pa1, pref, r)
  j = 0
  for i in 0..pa0.length-1
    c = pa0[i]
    if subs[j] == c
      r = i+pa1 if r == -1
      pref.concat(c)
      j += 1
    elsif subs[j-1] == c
      ## to ignore concurrent same characters
      r += 1 if r != -1
      next
    else
      pref = ""
      j = 0
      r = -1
    end
  end
  return [pref, r]
end