Fig. 5

Illustration of the proof of Theorem 13; we are scanning C with \(k = 2\). We illustrate the algorithm using the suffix trie of \(C'\): the suffix tree is obtained by compacting the unary paths into single edges, and then many of the suffix links become implicit; we draw the suffix-link from \(u_2\) to \(u^*\) with a dashed arrow. Following an implicit suffix link needs to be simulated using explicit suffix link from a parent. The cost of this can be amortized to the descending in the tree