Expresión regular para evitar 404s - consejos?

[rodobook]

Buenas, en una tienda online se han cambiado los enlaces de todos los productos al haber cambiado el sistema utilizado, por lo que me interesa hacer una redirección htaccess de los enlaces viejos a la búsqueda del nombre de esos productos.

ejemplo.

Enlace en google : www.tienda.com/producto-muy-bonito-p-4567.html

Lo que quiero es que al acceder a ese link, se redirija a search.php?search_query=producto+muy+bonito

Por ahora tengo lo siguiente:

RewriteRule ^([a-zA-Z0-9-]*)-p-([0-9]+)\.html /search.php?search_query=$1

Esto hace que la url

www.tienda.com/producto-muy-bonito-p-4567.html

se transforme en:

www.tienda.com/search?search_query=producto-muy-bonito

Como modifico mi expresión regular para que cambie además los - por + ? Hay que tener en cuenta que el numero de - es variable, la url puede ser tanto producto-muy-bonito como producto-bonito o producto-muy-bonito-y-largo

Gracias