By a completely similar approach we can compute \({\mathcal {G }}^{{\intercal }}_\alpha (w)\) , generalizing the algorithm of [1]}.
To this end, we construct \({\mathit {LCP}}\) -structures for \(w{w}^{{\intercal }}\)  (allowing us to test efficiently whether a factor \({w[i,j]}^{{\intercal }}\)  occurs at some position in \(w\) ).
When we search the \(\alpha \) -gapped palindromes \(u_\lambda ,v,u_\rho \)  (with \({u}_{{\rho }}\equiv {{u}_{{\lambda }}}^{{\intercal }}\) ), we split again \(w\)  in blocks and \(k\) -blocks, for each \(k\le \log |w|\) , to check whether there exists such an \(u_\lambda ,v,u_\rho \)  with \(2^{k}\le |u_\lambda |\le 2^{k+1}\) .
This search is conducted pretty much as in the case of repeats, only that now when we fix some factor \(y\)  of \(u_\rho \) , we have to look for the occurrences of \({y}^{{\intercal }}\)  in the factor of length \({\mathcal {O}}(\alpha |u_\rho |)\)  preceding it; the \({\mathit {LCP}}\) -structures for \(w{w}^{{\intercal }}\)  are useful for this, because, as explained above, they allow us to efficiently search the mirror images of factors of \(w\)  inside \(w\) .
Thus, given a word \(w\)  and \(\alpha \ge 1\) , we can compute \({\mathcal {G }}^{{\intercal }}_\alpha (w)\)  in time \({\mathcal {O}}(\alpha n)\) .
