Problem 90: Simple Anti-powers

$ \newcommand{\prpos}{\mathit{pp}}% \newcommand{\antip}{\mathit{antip}}% \newcommand{\alph}{\mathit{alph}}% \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} $

A dual notion of periodicity or local periodicity is that of anti-powers, which is introduced in the problem.

A word $u \in \{\sa{1},\sa{2},\dots,k\}^+$ is an anti-power if each of its letters appear exactly once in it. It is a permutation of a subset of the alphabet, that is, $\alph(u)=|u|$.

Show how to locate in time $O(n)$ anti-powers of length $k$ occurring in a word $x \in \{\sa{1},\sa{2},\dots,k\}^n$.

For example, $\sa{13542}$ and $\sa{54231}$ occur in $\sa{341354231332} \in \{\sa{1},\sa{2},\dots,5\}^+$ at positions $2$ and $4$ and are its only anti-powers of length $5$.

References

G. Badkobeh, G. Fici, and S. J. Puglisi. Algorithms for anti-powers in strings. Inf. Process. Lett., 137:57-60, 2018.

G. Fici, A. Restivo, M. Silva, and L. Q. Zamboni. Anti-powers in infinite words. J. Comb. Theory, Ser. A, 157:109-119, 2018.

T. Kociumaka, J. Radoszewski, W. Rytter, J. Straszynski, T. Walen, and W. Zuba. Efficient representation and counting of antipower factors in words. In C. Martín-Vide, A. Okhotin, and D. Shapira, editors, Language and Automata Theory and Applications - 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings, volume 11417 of Lecture Notes in Computer Science, pages 421-433. Springer, 2019.

125 Problems in Text Algorithms

Example

Simple anti-powers

Problem 90: Simple Anti-powers

References