In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.

The power in a string that mentioned below means some power which is one substring of the string. In addition, two strings are distinct if they don't look the same.

In Maxime Crochemore, et al. Number of Occurrences of powers in Strings, theorem 3 claims that "The number of distinct $k$-th powers, for a fixed integer $k \geq 3$, in a string of length $n$ is at most $\frac{n}{k-2}$".

If it is true, we may conclude the number of all distinct $k$-th powers for all integers $k \geq 3$ in a string of length $n$ is $\mathcal{O}(n \log n)$.

Is it possible to detect all these powers through some method in time complexity $\mathcal{O}(n \log n)$? For example, count the number of them and list one occurrence (start index and end index) for each of them.

I failed to seek results in recent research...

I asked the same question at here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.