On word equations in one variable

For a word equation E of length n in one variable x occurring #x times in E a resolution algorithm of O(n + #x log n) time complexity is presented here. This is the best result known and for the equations that feature #x < n/logn it yields time complexity of O(n) which is optimal. Additionally, we prove that the set of solutions of one-variable word equations is either of the form F where F is a set of O(logn) words or of the form F ∪ (uv)+ u where F is a set of O(logn) words and u, v are some words such that uv is a primitive word.