Linear systems with structures such as Toeplitz-, Vandermonde-or Cauchy-likeness can be solved in $O\,\tilde{~}(\alpha^2 n)$ operations, where $n$ is the matrix size, $\alpha$ is its displacement rank, and $O\,\tilde{~}$ denotes the omission of logarithmic factors. We show that for Toeplitz-like and Vandermonde-like matrices, this cost can be reduced to $O\,\tilde{~}(\alpha^{\omega-1} n)$, where $\omega$ is a feasible exponent for matrix multiplication over the base field. The best known estimate for $\omega$ is $\omega < 2.38$, resulting in costs of order $O\,\tilde{~}(\alpha^{1.38} n)$. We also present consequences for Hermite--Pad\'e approximation and bivariate interpolation.