@@ -6,39 +6,95 @@ const SEPARATOR = '$';
66 *@return {number[] }
77 */
88function buildZArray ( zString ) {
9- const zArray = new Array ( zString . length ) ;
9+ // Initiate zArray and fill it with zeros.
10+ const zArray = new Array ( zString . length ) . fill ( null ) . map ( ( ) => 0 ) ;
1011
11- let left = 0 ;
12- let right = 0 ;
13- let k = 0 ;
12+ // Z box boundaries.
13+ let zBoxLeftIndex = 0 ;
14+ let zBoxRightIndex = 0 ;
1415
15- for ( let i = 1 ; i < zString . length ; i += 1 ) {
16- if ( i > right ) {
17- left = i ;
18- right = i ;
16+ // Position of current zBox character that is also a position of
17+ // the same character in prefix.
18+ // For example:
19+ // Z string: ab$xxabxx
20+ // Indices: 012345678
21+ // Prefix: ab.......
22+ // Z box: .....ab..
23+ // Z box shift for 'a' would be 0 (0-position in prefix and 0-position in Z box)
24+ // Z box shift for 'b' would be 1 (1-position in prefix and 1-position in Z box)
25+ let zBoxShift = 0 ;
1926
20- while ( right < zString . length && zString [ right - left ] === zString [ right ] ) {
21- right += 1 ;
27+ // Go through all characters of the zString.
28+ for ( let charIndex = 1 ; charIndex < zString . length ; charIndex += 1 ) {
29+ if ( charIndex > zBoxRightIndex ) {
30+ // We're OUTSIDE of Z box. In other words this is a case when we're
31+ // starting from Z box of size 1.
32+
33+ // In this case let's make current character to be a Z box of length 1.
34+ zBoxLeftIndex = charIndex ;
35+ zBoxRightIndex = charIndex ;
36+
37+ // Now let's go and check current and the following characters to see if
38+ // they are the same as a prefix. By doing this we will also expand our
39+ // Z box. For example if starting from current position we will find 3
40+ // more characters that are equal to the ones in the prefix we will expand
41+ // right Z box boundary by 3.
42+ while (
43+ zBoxRightIndex < zString . length &&
44+ zString [ zBoxRightIndex - zBoxLeftIndex ] === zString [ zBoxRightIndex ]
45+ ) {
46+ // Expanding Z box right boundary.
47+ zBoxRightIndex += 1 ;
2248}
2349
24- zArray [ i ] = right - left ;
25- right -= 1 ;
50+ // Now we may calculate how many characters starting from current position
51+ // are are the same as the prefix. We may calculate it by difference between
52+ // right and left Z box boundaries.
53+ zArray [ charIndex ] = zBoxRightIndex - zBoxLeftIndex ;
54+
55+ // Move right Z box boundary left by one position just because we've used
56+ // [zBoxRightIndex - zBoxLeftIndex] index calculation above.
57+ zBoxRightIndex -= 1 ;
2658} else {
27- k = i - left ;
28- if ( zArray [ k ] < ( right - i ) + 1 ) {
29- zArray [ i ] = zArray [ k ] ;
59+ // We're INSIDE of Z box.
60+
61+ // Calculate corresponding Z box shift. Because we want to copy the values
62+ // from zArray that have been calculated before.
63+ zBoxShift = charIndex - zBoxLeftIndex ;
64+
65+ // Check if the value that has been already calculated before
66+ // leaves us inside of Z box or it goes beyond the checkbox
67+ // right boundary.
68+ if ( zArray [ zBoxShift ] < ( zBoxRightIndex - charIndex ) + 1 ) {
69+ // If calculated value don't force us to go outside Z box
70+ // then we're safe and we may simply use previously calculated value.
71+ zArray [ charIndex ] = zArray [ zBoxShift ] ;
3072} else {
31- left = i ;
32- while ( right < zString . length && zString [ right - left ] === zString [ right ] ) {
33- right += 1 ;
73+ // In case if previously calculated values forces us to go outside of Z box
74+ // we can't safely copy previously calculated zArray value. It is because
75+ // we are sure that there is no further prefix matches outside of Z box.
76+ // Thus such values must be re-calculated and reduced to certain point.
77+
78+ // To do so we need to shift left boundary of Z box to current position.
79+ zBoxLeftIndex = charIndex ;
80+
81+ // And start comparing characters one by one as we normally do for the case
82+ // when we are outside of checkbox.
83+ while (
84+ zBoxRightIndex < zString . length &&
85+ zString [ zBoxRightIndex - zBoxLeftIndex ] === zString [ zBoxRightIndex ]
86+ ) {
87+ zBoxRightIndex += 1 ;
3488}
3589
36- zArray [ i ] = right - left ;
37- right -= 1 ;
90+ zArray [ charIndex ] = zBoxRightIndex - zBoxLeftIndex ;
91+
92+ zBoxRightIndex -= 1 ;
3893}
3994}
4095}
4196
97+ // Return generated zArray.
4298return zArray ;
4399}
44100