Surnames play a key role as person natural identifiers, essentially in present information systems. This paper deals with the topic of optimizing a phonetic search algorithm as a string matching of surnames usable for communications service providers, person registries, social networks or genealogy databases. It describes a proposed solution for the phonetic searching of Slovak and (territorial) neighboring languages (Czech, Polish, Ukrainian, Russian, German, Hungarian, Jewish) surnames. This solution was designed to improve search precision and recall when searching for people by their surnames originating in these languages.