Renombrar masivamente

[eeeee]

Hola a todos:
Tengo una carpeta en la que dentro hay otras 35 carpetas más.
En total hay 500.000 fotos y todos los nombres están separadas por guión bajo (_) .

Necesito hacer un código que las recorra todas y renombre el guión bajo por _-_ en el lugar en que parte de la cadena es diferente
Voy a poner por ejemplo tres cadenas.

the_rolling_stones_forty_licks_back.jpg
the_rolling_stones_the_last_nearness_back.jpg
the_rolling_stones_the_singles_back.jpg

Pues necesito que el código detecte a esta parte de la cadena the_rolling_stones_ y renombrarla a the_rolling_stones_-_ y aquí lo que siga.
tambien tiene que detectar a otras cadenas que pueden ser escritas por error o correctas, por ejemplo:

the_rolling_forty_licks_back.jpg
the_rolling_the_last_nearness_back.jpg
the_rolling_the_singles_back.jpg
En este caso tiene que resultar the_rolling_-_ y lo que siga.

O sea que detecte hasta que parte de la cadena es igual a la anterior para renombrar el _ por _-_

La parte del código de recorrer las carpetas y renombrar los archivos, se como hacerla. Sólo me hace falta el script para detectar hasta que parte es igual el nombre.

Espero haberme explicado bien y que alguien pueda ayudarme.

Gracias