# Algorithms to factorize words into product of powers

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.

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.