If s ends with some digits, then root_and_index s = (root,i) such that i is the biggest integer such that s = root^string_of_int i. Otherwise, root_and_index s = (s,-1).

Assume that root_and_index p = (r,i). If i<0 then get_safe_prefix p idmap returns p,StrMap.add p (-1) idmap and, for all non-negative integer k, StrSet.mem (p^string_of_int k) (strings idmap')=false. Otherwise, get_safe_prefix p idmap returns r^string_of_int k,StrMap.add r k idmap, where k is greater than or equal to i and 1 + the index of r in idmap.