5 * Fill z with Z-box information for s. String z will not be resized
6 * and will only be filled up to its size cap. This is the linear-time
7 * algorithm from Gusfield. An optional sanity-check uses a naive
8 * algorithm to double-check results.
11 void calcZ(const T& s,
15 bool sanityCheck = false)
17 size_t lCur = 0, rCur = 0;
18 size_t zlen = length(z);
19 size_t slen = length(s);
22 //assert_leq(zlen, slen);
23 for (size_t k = 1; k < zlen && k+off < slen; k++) {
25 assert(z[lCur] == 0 || z[lCur] == rCur - lCur + 1);
27 // compare starting at k with prefix starting at 0
29 while(off+ki < length(s) && s[off+ki] == s[off+ki-k]) ki++;
31 assert_lt(off+z[k], slen);
37 // position k is contained in a Z-box
38 size_t betaLen = rCur - k + 1;
39 size_t kPrime = k - lCur;
40 assert_eq(s[off+k], s[off+kPrime]);
41 if(z[kPrime] < betaLen) {
43 assert_lt(off+z[k], slen);
44 // lCur, rCur unchanged
45 } else if (z[kPrime] > 0) {
47 while (off+q+rCur+1 < length(s) && s[off+q+rCur+1] == s[off+betaLen+q]) q++;
49 assert_lt(off+z[k], slen);
55 assert_lt(off+z[k], slen);
56 // lCur, rCur unchanged
62 // Recalculate Z-boxes using naive quadratic-time algorithm and
63 // compare to linear-time result
65 for(size_t i = 1; i < length(z); i++) {
67 for(j = i; off+j < length(s); j++) {
68 if(s[off+j] != s[off+j-i]) break;