One-Variable Word Equations in Linear Time
Artur Jeż · Algorithmica · 2014
In this paper we consider word equations with one-variable (and arbitrarily many occurrences of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case the recompression is nondeterministic in case of one-variable it becomes deterministic and its running time is $$\mathcal {O}(n + \#_X \log n)$$ , where $$\#_X$$ is the number of occurrences of the variable in the equation. This matches the previously best algorithm due to Dąbrowski and Plandowski. Then, using a couple of heuristics as well as more detailed time analysis, the running time is lowered to $$\mathcal {O}(n)$$ in the RAM model. Unfortunately, no new properties of solutions are shown.