CLR cover
Previous problem

Problem 64: Counting Factors Covering a Position

Next problem
\( \newcommand{\Fac}{\mathcal{C}}% \newcommand{\NFac}{\mathcal{N}}% \newcommand{\prefixsum}{\mathit{prefix\_sum}}% \newcommand{\Count}{\mathit{Count}}% \newcommand{\weig}{\mathit{weight}}% \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \)

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.