Очень долго долбался с задачей "String Similarity" с сайта InterviewStreet. И так, и эдак ковырял, но удавалось уложиться только в 8 тестов из 10.
А на самом деле оказалось, что нужно просто применить Z-функцию. Мда, пошел читать букварь... Кстати, не могу найти английское название Z-функции. Если кто знает, напишите, плз.
З.Ы. На Хабре можно почитать хороший разбор алгоритмов поиска подстрок.
