Как быть с вариантами 6 и 11, в перворм приближении, хз.
В остальных случаях, если интересует "хотя бы частичное совпадение", я бы предложил перевести все в нижний регистр, представить, что у вас есть "3 элемента (составляющих)". Один из них - фамилия. Другие - имя и отчество (неважно, какой порядок, инициалы или полное и т.д.). А далее - сравнивать с заранее подготовленной базой фамилий. Думаю, для русскоязычного населения, для 80% случаев, этот список все же будет не сильно большим.
Алгоритм таков примерно. Нашли среди трех элементов слово, подходящее под фамилию. Дальше проверяете оставшиеся два элемента. Сначала по полному совпадению (как вариант, алгоритмом нечеткого сравнения и пробуя подобрать желаемый порог), если не помогло - по инициалам.
Мне кажется, кое-как результат может быть удовлетворительным (для первого приближения, плюс - реализация не так сложна для проверки). А дальше уже отталкиваться от эффективности и поставленных целей.
Средний
