Class name: ZBox
Method name: getZBox
Parameters: String,int
Returns: int
The Z function is defined as follows. Let S be a string, and n be the length
of that string. For any i such that 0 <= i < n, Zi(S) is defined to be the
length of the longest prefix of S[i..n] (the substring of S beginning at
position i and ending with the character at position n - 1) that matches a
prefix of S. That is, Zi(S) is the number of characters at and following
position i that match corresponding characters from the beginning of the
string. Comparisons should be case sensitive.
(For the purposes of defining this function, strings are indexed starting at 0,
so that i = 0 refers to the first character, i = 1 refers to the second
character, and so on).
Note that Z0(S) = n for any string. A few more examples are in order:
S = "aabcaabca"
i = 0,1,2,3,4,5,6,7, and 8
n = 9
Z0(S) = 9
Z1(S) = 1 (S[1..1] = S[0..0] = "a")
Z2(S) = 0
Z3(S) = 0
Z4(S) = 5 (S[4..8] = S[0..4] = "aabca")
Z5(S) = 1 (S[5..5] = S[0..0] = "a")
Z6(S) = 0
Z7(S) = 0
Z8(S) = 1 (s[8..8] = S[0..0] = "a")
Implement a class named ZBox that provides a method named getZBox, which takes
a String and an int as parameters. The method signature is:
public int getZBoxes(String string, int i);
The String will be at least one character in length and at most 50 characters
in length.
The String will contain only letters.
The value of i will be a non-negative integer less than the length of string.
The method should return the value of Zi(string), which is the length of the
Z-box that exists at position i in the given string.
Examples:
- If S = "lessonletter" and i = 6, the first two letters of the substring
starting at 6 ("letter") match the first two letters of the entire string so
the method should return 2.
- If S = "lessonLetter" and I=6, the method should return 0.
- If S = "hereisastring" and i = 2, no prefix of "reisastring" matches a prefix
of "hereisastring" so the method should return 0.
- If S = "testtest" and i = 4, the substring starting at 4 ("test") matches the
first four characters of the entire string, so the method should return 4.
- If S = "aabcaabca" and i = 4, the method should return 5
- If S = "aabcaabca" and i = 0, the method should return 9
- If S = "aabcaabca" and i = 3, the method should return 0
|