Pesquisar na Comunidade

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!