(S: T_LENGTH_SUB_AND_SEARCH_REV) = struct
let split t ~on =
let length_of_t = S.length t in
begin match on with
| `Character c ->
let rec loop acc from =
match S.index_of_character_reverse t ~from c with
| Some index when index = length_of_t - 1 ->
loop (S.empty :: acc) (index - 1)
| Some index ->
loop (S.sub_exn t ~index:(index + 1) ~length:(from - index) :: acc)
(index - 1)
| None ->
S.sub_exn t ~index:0 ~length:(from + 1) :: acc
in
loop [] (length_of_t - 1)
| `String s ->
let length_of_s = S.length s in
let rec loop acc from =
match S.index_of_string_reverse t ~from ~sub:s with
| Some index when index = length_of_t - length_of_s ->
loop (S.empty :: acc) (index - 1)
| Some index ->
let offset = index + length_of_s in
let length = from - offset + 1 in
loop (S.sub_exn t ~index:offset ~length :: acc) (index - 1)
| None ->
S.sub_exn t ~index:0 ~length:(from + 1) :: acc
in
if length_of_s > 0
then loop [] (length_of_t - 1)
else if length_of_t = 0
then [ t ]
else begin
let res = ref [] in
for index = length_of_t - 1 downto 0 do
res := S.sub_exn t ~index ~length:1 :: !res
done;
!res
end
end
end