Algorithms to factorize words into product of powers

Question

I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references.

Let $A$ be a finite set of symbols, are there efficient algorithms that take as input a word $w$ over $A$ and return as output a representation of $w$ in terms of product of powers? If so, what are their computational complexities?

Of course, this representation is not unique, for example for $A = \{0,1\}$ we have $$0101010010010 = (01)^3 (001)^2 0 = (01)^2 (010)^3 ,$$ so they might be algorithms that impose further restrictions on the exponents or on the lengths of the bases of the powers.

Also, to avoid trivialities, if $w$ can be written as a product of powers of words with at least a power with exponent $>1$, then such algorithms should be able to find one of such representations (otherwise, obviously, we always have $w = w^1$).

Thanks for help.

Answer 1

Unfortunately, I couldn't easily find a paper that solves exactly this problem.

But I believe the algorithm from Factorizing Strings into Repetitions can be adapted to solve the problem. They find a factorization into repetitions, meaning that $s = s_1 s_2 \dots s_k$, where each factor $s_i$ can be represented as $s_i = x^k x'$ for some string $x$, where $k \geq 2$ and $x'$ is a prefix of $x$.

Their algorithm consists of an efficient dynamic programming simulation and it likely can be modified to get rid of $x'$ and $k \geq 2$ constraint, while asking for the minimum number of factors.