TopCoder problem "ZBox" used in SRM 22 (Division I Level One , Division II Level One)

Problem Statement

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.

- 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


Parameters:String, int
Method signature:int getZBox(String param0, int param1)
(be sure your method is public)

Problem url:

Problem stats url:




Problem categories: