Problem 64: Counting Factors Covering a Position


A factor of a word $x$ covers a position $k$ on $x$ if it has an occurrence $x[i\dd j]$ that satisfies $i\leq k\leq j$.

Let $\Fac(x,k)$ denote the number of (distinct) factors of $x$ covering the position $k$ and let $\NFac(x,k)$ denote the number of factors having an occurrence that does not cover $k$.

Show how to compute in linear time $\Fac(x,k)$ and $\NFac(x,k)$ for a given position $k$ on $x$, assuming a constant-size alphabet.

References

• D. Kempa, A. Policriti, N. Prezza, and E. Rotenberg. String attractors: Verification and optimization. CoRR, abs/1803.01695, 2018.
• S. Mantaci, A. Restivo, G. Romana, G. Rosone, and M. Sciortino. String attractors and combinatorics on words. CoRR, abs/1907.04660, 2019.
• G. Navarro and N. Prezza. Universal compressed text indexing. Theor. Comput. Sci., 762:41-50, 2019.
• N. Prezza. String attractors. CoRR, abs/1709.05314, 2017.