\Section{Суффиксный массив за $\O(n \log n)$ и LCP}{23 октября}{Олег Свидченко}

\Subsection{Суффиксный массив за $\O(n \log n)$}

{\bf Что сортируем?}\\
Поймем, что не имеет значения, сортируем мы суффиксы или циклические сдвиги\\
Сдвиги $\to$ суффиксы: $s \to s\NO{}$ ($\NO{}$ - символ, который меньше всего алфавита)\\
Суффиксы $\to$ сдыиги: $s \to ss$\\
Отсортируем теперь циклические сдвиги.\\

{\bf Алгоритм за $\O(n^{2} + \Sigma)$}\\
Цифровая сортировка.\\
Пусть уже отсортировали все подстроки длины $k$ в циклической строке.\\
Переход $k \to k + 1$ выполняем за $\O(n)$.\\

{\bf Улучшение до $\O(n \log n)$}\\
Будем делать переход $k \to 2 \cdot k$.\\
Пусть $p[i]$ - указатели на начало подстрок длины $k$ в отсортированном порядке.\\
$color[j]$ - числа, обладающие свойством $color[p[i]] \leq color[p[i + 1]]$, причем равенство достигает только в случае равенства строк.\\
Отсортировать подстроки длины $2 \cdot k$ значит отсортировать $\q{ color[j], color[j + k] }$\\
Отсортируем их за $\O(n)$ (числа от $0$ до $n-1$, мы так хотим)\\
Получили новый отсортированный порядок. Осталось только пересчитать $color$\\\\
\begin{code}
    c = 0;
    for (j = 0 .. n - 1)
        //"j && .." `здесь означает, что j != 0` 
        if j && pair[p[j]] != pair[p[j - 1]]
            c++;
        color[p[j]] = c;
\end{code}

{\bf Сортируем пары за $\O(n)$}
\begin{code}
    for (i = 0 .. n - 1)
        cnt[color[j]]++;
    for (j = 1 .. n - 1)
        pos[j + 1] = pos[j] + cnt[j];
    for (j = 0 .. n - 1)
        i = ((p[j] - k) + n) \% n; // `переход на k символов левее`
        p_new[pos[color[i]]++] = i;
        // `все и так отсортировано по второй половине`
        // `достаточно стабильно отсортировать по первой`
\end{code}

\Subsection{Суффиксный массив и LCP}

{\bf Алгоритм Касаи}\\
Начинаем считать с самого большого суффикса.\\
Мы знаем, что $LCP[p^{-1}[j]] \geq LCP[p^{-1}[j - 1]] - 1$ ($p^{-1}$ по суффиксу возвр. его позицию в суффмассе)\\
Будем честно считать $LCP[i]$, но начиная с $LCP[i - 1] - 1$ позиции.\\\\
\begin{code}
    for (i = 0 .. n - 1)
        p2[p[i]] = i;
    k = 0;
    for (j = 0 .. n - 1)
        i = p2[j];
        k--;
        if (k < 0 || i == n-1)
            k = 0;
        if (i != n - 1) 
            while (s[p[i] + k] == s[p[i + 1] + k])
                k++;
        lcp[i] = k;
\end{code}

\begin{Lm}
    $Time = \O(n)$
    \begin{proof}
        $k$ суммарно уменьшится не более чем на $2 \cdot n$\\
        $k \leq n$ (КО)\\
    \end{proof}
\end{Lm}
