Let $x_1, x_2, \ldots, x_n$ be called "characters".
Re-construct the polynomial as a series of "atoms" separated by addition/subtraction operations.
For each character, count the number of atoms in which it appears. Group the atoms in which each character appears, and factor out the character. Repeat recursively.
If $n$ is your number of characters, and $m$ is the maximal degree, this algorithm should be $\mathcal{O}(n^2m)$. In practice, you should get better than that as long as your polynomials aren't very complicated.
I don't know if this is optimal. But it is an algorithm.
Edit:
Actually, upon further reflection, I believe this could be implemented very similarly to a depth-first search algorithm, in which case you could consider $x_1^m$ to be $m$ characters, and perhaps consider each character a node, possibly meaning that the total order would be $\mathcal{O}(mn)$. However, it is currently far too late for me to better analyze this approach; it would be greatly appreciated if these musings could be verified.