Buscar profissionais por cidade em PHP e MySQL

Galera... Todo mundo bem???

Estou com um projeto em PHP, nele existe um campo de busca que o usuário vai preencher com algo mais ou menos assim "Médico em São Paulo", a partir daí o sistema mostra pra ele todos os médicos da cidade. O problema é que minha pouca experiencia não me deixa pensar em uma lógica pra isso. Implementei uma com os seguintes passos:

-

Separa com explode() todas as palavras e coloca elas em um array;

- Exclui do array as palavras de ligação como "de", "da";

• Verifica no banco de dados se as palavras restantes são profissões.
• Salva em outro array as palavras que são profissões e exclui do atual;

As palavras restantes forma (na teoria) o nome da cidade então basta busca no banco os médicos com essa cidade em seu endereço. O problema está aí. Se a cidade tem nome simples (Curitiba por exemplo), funciona perfeitamente. Mas se tem nome composto não funciona, por exemplo São Paulo, eu teria duas palavras restante no array, e não faço ideia de como usar uso pra buscar a palavra certa... já pensei em usar o LIKE, mas vejam:

"SELECT * FROM profissionais WHERE localidade LIKE '%".$cidade1."%' and '%".$cidade2."
A posição das cidades no like não me garante que terei a cidade desejada. Alguém tem um ideia de como implementar, pode ser complementando a minha ou até ideia o processo como um todo?

Agradeço!