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.