StringContents

In many languages strings are represented by immutable data structures. This means that the location where the string contents are stored in memory may not be altered. In some situations, this leads to a large number of similar strings being stored and wasting memory. In this problem, you will consider the situation where a number of strings need to be stored in memory. However, to save space, if one string is a substring of another one, the system may forego storing the shorter string in memory. Instead, it may simply store the offset and length of the shorter string, along with a pointer to the longer string. For example, if given {"abcde","bcd"}, only the first string, "abcde", needs to be stored. The second string may be stored as a pointer to the first string, along with the pair (1,3) - the offset and length of "bcd" in "abcde". If a number of strings are identical, at least one copy must be stored, while the rest may be stored as an offset and length.

You will be given a String[], s, representing a number of Strings stored in this way. Each element of s will have one of two forms. If an entire string is stored, then an element of s will be a sequence of zero or more lowercase letters. If a string is stored as an offset and length, then an element of s will be formatted as "PTR OFF LEN", where PTR is a 0 based index into s indicating the reference string, and OFF (indexed from 0) and LEN are the offset and length of this string in s[PTR]. For example, {"abcde","0 1 3"} would indicate that element 1 of s had the value of "bcd", since the substring with length 3 starting at position 1 of element 0 of s is "bcd". Given s, your method should find the values of all the strings, and return the result as a String[]. For example, {"abcde","0 1 3"} would return {"abcde","bcd"}. If the input is invalid, you should return the empty String[]. The input is invalid if any PTR refers to an element that does not exist, or to an element of s that is not a sequence of lowercase letters. It is also invalid if OFF or LEN are less than 0, or if OFF+LEN is greater than the length of the string.