5 июня 2012 г.

String Similarity

Очень долго долбался с задачей "String Similarity" с сайта InterviewStreet. И так, и эдак ковырял, но удавалось уложиться только в 8 тестов из 10.

А на самом деле оказалось, что нужно просто применить Z-функцию. Мда, пошел читать букварь... Кстати, не могу найти английское название Z-функции. Если кто знает, напишите, плз.

З.Ы. На Хабре можно почитать хороший разбор алгоритмов поиска подстрок.