Если вы не знаете, что такое префикс-функция строки, не знаете, как она вычисляется, или, что самое главное, не до конца понимаете, почему алгоритм вычисления префикс-функции работает за линейное время, то эта статья для вас.
Я прошел через череду осознаний и озарений, прежде чем достичь просветления, и теперь предлагаю вам пройти этот путь вместе со мной.
Этап 1. Определение
Первое мое знакомство с префикс-функцией произошло еще в школе. Я готовился к олимпиадам по программированию, и конечно же в моем "джентльменском наборе" подготовки был алгоритм Кнута-Морриса-Пратта, который позволяет найти подстроку длины Читать полностью »