Бордеры и префикс-функция

Бордер строки $s$ — это её префикс, совпадающий с суффиксом той же длины.

У строки abacaba бордеры — a, aba и вся строка целиком. Последний вариант неинтересен, поэтому дальше речь только о собственных бордерах: тех, что короче всей строки.

Префикс-функция $\pi[i]$ — длина наибольшего собственного бордера префикса $s[0..i]$.

Для abacaba она равна $0, 0, 1, 0, 1, 2, 3$.

Лемма, из которой всё следует

При дописывании одного символа наибольший бордер удлиняется не более чем на единицу: $\pi[i+1] \le \pi[i] + 1$.

Доказательство от противного. Пусть у префикса длины $i+2$ нашёлся бордер длины хотя бы $\pi[i] + 2$. Отбросим у него последний символ спереди и сзади — получится бордер префикса длины $i+1$ длины хотя бы $\pi[i] + 1$. Но $\pi[i]$ — наибольший. Противоречие.

Отсюда сразу видно, что делать: у нас есть кандидат $\pi[i] + 1$, и если он не подошёл, надо перебирать кандидатов по убыванию.

Какие кандидаты перебирать

Наивно можно было бы уменьшать длину на единицу. Это работает, но медленно — и лишнее.

Ключевое наблюдение: если строка длины $k$ является бордером префикса, то следующий по величине кандидат — это $\pi[k-1]$, наибольший бордер самого этого бордера.

Почему при этом ничего не теряется. Пусть есть бордер длины $m$, где $\pi[k-1] < m < k$. Он одновременно префикс и суффикс всей рассматриваемой строки, а раз он короче $k$, то лежит и внутри бордера длины $k$ — и там тоже является одновременно префиксом и суффиксом. Значит, $m$ — бордер строки длины $k$, и $m \le \pi[k-1]$. Противоречие.

То есть все бордеры строки — это в точности цепочка $\pi[n-1],\ \pi[\pi[n-1]-1],\ \ldots$ до нуля. Перебирать что-то между её звеньями бессмысленно.

Код

vector<int> prefixFunction(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int len = pi[i - 1];                       // кандидат: бордер предыдущего префикса
        while (len > 0 && s[i] != s[len]) len = pi[len - 1];
        if (s[i] == s[len]) len++;
        pi[i] = len;
    }
    return pi;
}

Десять строк. Проверено: на 40 000 случайных строк результат совпал с прямым поиском наибольшего бордера перебором длин.

Почему это линия, а не квадрат

Внутри for стоит while, который в теории может прокрутиться $n$ раз. Но суммарно по всем итерациям он сделает не больше $n$ шагов.

Следите за величиной len. Каждая итерация внешнего цикла увеличивает её не более чем на единицу — это ровно та лемма, с которой мы начали. Каждый шаг внутреннего while уменьшает её хотя бы на единицу. Уменьшить в сумме больше, чем прибавили, нельзя, а прибавили не больше $n$.

Тот же приём, что в очереди на двух стеках и в стеке ближайших меньших: считаем не отдельную операцию, а суммарную работу.

Измерено — сколько шагов внутренний цикл делает на самом деле:

строка	длина	шагов	доля от $n$
aaaa…	1 000 000	0	0,00
строка Фибоначчи	1 346 269	27	0,00
случайная, алфавит 26	1 000 000	38 282	0,04
случайная, алфавит 2	1 000 000	420 611	0,42
подобранная периодическая	200 000	198 293	0,99

Оценка «не больше $n$» — не запас, а почти точная граница: на специально подобранной периодической строке доля доходит до 0,99. Зато aaaa… и строка Фибоначчи, которые кажутся тяжёлыми, обходятся почти без откатов: там len растёт монотонно.

Что ещё сразу известно

Наименьший период строки равен $n - \pi[n-1]$.

Это тот же критерий, что в статье про период: $d$ — период тогда и только тогда, когда строка совпадает с собой, сдвинутой на $d$. А сдвиг на $d$ совпадает ровно тогда, когда есть бордер длины $n - d$. Наибольшему бордеру отвечает наименьший период.

Через хеши то же самое ищется за $O(n \log n)$ перебором сдвигов; префикс-функция даёт ответ за $O(n)$ и без вероятностных допущений.

Все периоды — это $n$ минус длины всех бордеров, то есть та самая цепочка $\pi[n-1], \pi[\pi[n-1]-1], \ldots$

Сколько раз каждый префикс встречается в строке считается одним обратным проходом по $\pi$: прибавляем счётчик позиции к счётчику её бордера, идя справа налево.