\Section{Суффиксный массив}{16 октября 2017}{Сергей Копелиович}

\begin{Def}
Суффиксный массив $s$ -- отсортированный массив суффиксов $s$.
\end{Def}

Суффиксы сортируем в лексикографическом порядке.
Каждый суффикс однозначно задается позицией начала в $s \SO$ 
на выходе мы хотим получить перестановку чисел от $0$ до $n{-}1$.

\THE{Тривиальное решение:} \t{std::sort} отработает за $\O(n \log n)$ операций `\t{<}' $\SO$ за $\O(n^2 \log n)$.

\up
\Subsection{Построение за $\O(n \log^2n)$ хешами}

Мы уже умеем сравнивать хешами строки на равенство, научимся сравнивать их на ``\t{>/<}''.

Бинпоиском за $\O(\log(min(|s|, |t|)))$ проверок на равенство найдём $x = lcp(s,t)$.\\
Теперь $less(s, t) = (s[x] < t[x])$. Кстати, в \t{C/C++} после строки всегда идёт символ с кодом $0$.

\down
Получили оператор меньше, работающий за $\O(\log n)$ и требующий $\O(n)$ предподсчёта.

Итого: суффмассив за $\O(n + (n \log n) \cdot \log n) = \O(n \log^2 n)$.

\down
При написании сортировки нам нужно теперь минимизировать в первую очередь именно число сравнений $\SO$
с точки зрения \t{C++::STL} быстрее будет работать \t{stable\_sort} (MergeSort внутри).

\begin{Rem}
Заодно научились за $\O(\log n)$ сравнивать на больше/меньше любые \underline{подстроки}.
\end{Rem}

\up
\Subsection{Применение суффиксного массива: поиск строки в тексте}

{\bf Задача:} дана строка $t$, приходят строки-запросы $s_i$: ``является ли $s_i$ подстрокой $t$''.

\down
Предподсчёт: построим суффиксный массив $p$ строки $t$. 

%Отвечать на запрос будем бинпоиском:
%($s_i$ -- подстрока $t$) $\EQ$ ($s_i$ является началом какого-то суффикса $t$).
В суффиксом массиве сначала лежат все суффиксы $< s_i$, затем $\ge s_i \SO$
бинпоиском можно найти $\min k \colon\ t[p_k{:}] \ge s_i$. 
Осталось заметить, что ($s_i$ -- префикс $t[p_k{:}]$) $\EQ$ ($s_i$ -- подстрока $t$).

\down
Внутри бинпоиска можно сравнивать строки за линию, получим время $\O(|s_i| \log |t|)$ на запрос.

Можно за $\O(\log |t|)$ с помощью хешей, для этого нужно один раз предподсчитать хеши для $t$, а при ответе 
на запрос насчитать хеши $s_i$. Получили время $\O(|s_i|+\log |t| \cdot \log |s_i|)$ на запрос.

\down
В \autoref{sec@sufarraysearch} мы улучшим время обработки запроса до $\O(|s_i| + \log |t|)$.

\Subsection{Построение за $\O(n^2)$ и $\O(n \log n)$ цифровой сортировкой}

Заменим строку \t{s} на строку \t{s\NO}, где \NO{} -- символ, лексикографически меньший всех в \t{s}.

Будем сортировать циклические сдвиги \t{s\NO}, порядок совпадёт с порядком суффиксом. 

Длину \t{s\NO} обозначим $n$.

\down
{\bf Решение за $\O(n^2)$:} цифровая сортировка.\\
Сперва подсчётом по последнему символу, затем по предпоследнему и т.д.\\
Всего $n$ фаз сортировок подсчётом. В предположении $|\Sigma| \le n$ получаем время $\O(n^2)$. \\
Суффмассив, как и раньше задаётся перестановкой начал... теперь циклических сдвигов.

\down
{\bf Решение за $\O(n \log n)$:} цифровая сортировка с удвоением длины.

Пусть у нас уже отсортированы все подстроки длины $k$ циклической строки \t{s\NO}. 

Научимся за $\O(n)$ переходить к подстрокам длины $2k$.

Давайте требовать не только отсортированности но и знания ``равны ли соседние в отсортированном порядке''.
Тогда линейным проходом можно для каждого $i$ насчитать тип (цвет) циклического сдвига 
$c[i] \colon (0 \le c[i] < n) \wedge (\t{s[i:i+k)} < \t{s[j:j+k)} \EQ c[i] \le c[j])$.

\down
Любая подстрока длины $2k$ состоит из двух половин длины $k \SO$ \\
переход $k \to 2k$ -- цифровая сортировка пар $\q{c[i],c[i{+}k]}$.

\down
Прекратим удвоение $k$, когда $k \ge n$. Порядки подстрок длины~$k$ и $n$ совпадут.

\begin{Rem}
В обоих решениях в случае $|\Sigma| > n$ нужно первым шагом отсортировать и перенумеровать символы строки.
Это можно сделать за $\O(n \log n)$ или за $\O(n + |\Sigma|)$ подсчётом.
\end{Rem}

\down
{\bf Реализация решения за $\O(n \log n)$.}

\t{p[i]} -- перестановка, задающая порядок подстрок длины \t{s[i:i+k)} циклической строки \t{s\NO}.

\t{c[i]} -- тип подстроки  \t{s[i:i+k)}.

За базу возьмём $k=1$
\begin{code}
bool sless( int i, int j ) { return s[i] < s[j]; }
sort(p, p + n, sless);
cc = 0; // `текущий тип подстроки`
for (i = 0; i < n; i++) // `тот самый линейный проход, насчитываем типы строк длины $1$`
	cc += (i && s[p[i]] != s[p[i-1]]), c[p[i]] = cc;
\end{code}
 
Переход: (у нас уже отсортированы строки длины $k$) $\SO$ (уже отсортированы строки длины $2k$ по второй половине) 
$\SO$ (осталось сделать сортировку подсчётом по первой половине).

\begin{code}
// `pos -- массив из $n$ нулей`
for (i = 0; i < n; i++)
	pos[c[i] + 1]++; // `обойдёмся без лишнего массива \t{cnt}`
for (i = 1; i < n; i++)
	pos[i] += pos[i - 1];
for (i = 0; i < n; i++) { // `p[i] -- позиция начала второй половины`
	int j = (p[i] - k) mod n; // `j -- позиция начала первой половины`
	p2[pos[c[j]]++] = j; // `поставили подстроку s[j,j+2k) на правильное место в p2`
}
cc = 0; // `текущий тип подстроки`
for (i = 0; i < n; i++) // `линейным проходом насчитываем типы строк длины $2k$`
	cc += (i && pair_of_c(p2[i]) != pair_of_c(p2[i-1]])), c2[p2[i]] = cc;
c2.swap(c), p2.swap(p); // `не забудем перейти к новой паре (p,c)`
\end{code}

Здесь \t{pair\_of\_c(i)} -- пара $\q{\t{c[i]}, \t{c[(i + k) mod n]}}$ 
(мы сортировали как раз эти пары!).

\down
\begin{Rem}
При написании суффмассива в контесте рекомендуется, прочтя конспект, написать код самостоятельно, без подглядывания в конспект.
\end{Rem}

\up
\Subsection{LCP за $\O(n)$: алгоритм Касаи}

Алгоритм Касаи считает LCP соседних суффиксов в суффиксном массиве. Обозначения: 

\down
$\bullet\ $ $p[i]$ -- элемент суффмассива, \\
$\bullet\ $ $p^{-1}[i]$ -- позиция суффикса \t{s[i:]} в суффмассиве, \\
$\bullet\ $ $next_i = p[p^{-1}[i]+1]$, $lcp_i = \text{LCP}(i, next_i)$. Наша задача -- насчитать массив $lcp_i$.

\begin{Prop}\label{prop@sufarrayseg}
Если у $i$-го и $j$-го по порядку суффикса в суффмассиве совпадают первые $k$ символов, 
то на всём отрезке $[i,j]$ суффмассива совпадают первые $k$ символов.
\end{Prop}

\begin{Lm}
Основная идея алгоритма Касаи: $lcp_i > 0 \SO lcp_{i+1} \ge lcp_i - 1$.
\end{Lm}
\begin{proof}
Отрежем у \t{s[i:]} и \t{s[next$_i$:]} по первому символу.\\
Получили суффиксы \t{s[i+1:]} и какой-нибудь \t{r}.\\
(\t{s[i:]} $\not=$ \t{s[next$_i$:]}) $\wedge$ (первый символ у них совпадал) $\SO$ \\
(\t{r} в суффмассиве идёт после \t{s[i+1:]}) $\wedge$ (у них совпадает первых $lcp_i{-}1$ символов) $\overset{\autoref{prop@sufarrayseg}}{\SO}$ \\
у \t{s[i+1:]} и \t{s[next$_{i+1}$]} совпадает хотя бы $lcp_i{-}1$ символ $\SO lcp_{i+1} \ge lcp_i-1$.
\end{proof}

Собственно алгоритм заключается в переборе $i \searrow$ и подсчёте $lcp_i$ начиная с $\max(0, lcp_{i+1}{-}1)$.

\down
{\bf Задача:} уметь выдавать за $\q{\O(n), \O(1)}$ LCP любых двух суффиксов строки $s$.

\down
{\bf Решение:} используем Касаи для соседних, а для подсчёта LCP любых других считаем RMQ.\\
RMQ мы решили в прошлом семестре. Например, Фарах-Колтоном-Бендером за $\q{\O(n), \O(1)}$. 

%\down
\Subsection{Построение за $\O(n)$: алгоритм Каркайнена-Сандерса}

На вход получаем строку $s$ длины $n$, при этом $0 \le s_i \le \frac{3}{2}n$.\\
Выход -- суффиксный массив. Сортируем именно суффиксы, а не циклические сдвиги.

\down
Допишем к строке 3 нулевых символа. Теперь сделаем новый алфавит: $w_i = (s_i, s_{i + 1}, s_{i + 2})$. 

Отсортируем $w_i$ цифровой сортировкой за $\O(n)$, перенумеруем их от $0$ до $n{-}1$.

Запишем все суффиксы строки $s$ над новым алфавитом: 

\down
$t_0 = w_0w_3w_6\dots$ \\
$t_1 = w_1w_4w_7\dots$ \\
$t_2 = w_2w_5w_8\dots$ \\
$\dots$\\
$t_{n-1} = w_{n-1}$

\down
Про суффиксы $t_{3k+i}$, где $i \in \{0, 1, 2\}$, будем говорить ``суффикс $i$-типа''.

\down
Запустимся рекурсивно от строки $t_0t_1$. Длина $t_0t_1$ не более $2\lceil\frac{n}{3}\rceil$. 

Теперь мы умеем сравнивать между собой все суффиксы $0$-типа и $1$-типа.

\down
Суффикс $2$-типа \t{=} один символ \t{+} суффикс $0$-типа $\SO$ \\
их можно рассматривать как пары и отсортировать за $\O(n)$ цифровой сортировкой.

\down
Осталось сделать merge двух суффиксных массивов. \\
Операция merge работает за линию, если есть ``\t{operator <}'', работающий за $\O(1)$.\\
Нужно научиться сравнивать суффиксы $2$-типа с остальными за $\O(1)$.

\down
$\forall i, j \colon t_{3i+2} = s_{3i+2}t_{3i+3}$, $t_{3j} = s_{3j}t_{3j+1} \SO$ чтобы сравнить суффиксы 
$2$-типа и $0$-типа, \\
достаточно уметь сравнивать суффиксы $0$-типа и $1$-типа. Умеем.

\down
$\forall i, j \colon t_{3i+2} = s_{3i+2}t_{3i+3}$, $t_{3j+1} = s_{3j+1}t_{3j+2} \SO$ чтобы сравнить суффиксы 
$2$-типа и $1$-типа, \\
достаточно уметь сравнивать суффиксы $0$-типа и $2$-типа. Только что научились.

% $\q{1\text{-типа},0\text{-типа}}$, их мы сравнивать умеем.
% А пара $\q{2\text{-типа},0\text{-типа}}$ перейдёт в пару $\q{1\text{-типа},2\text{-типа}}$, которую мы только что сравнили.

\pagebreak
\vspace*{-1.8em}
\THE{Псевдокод.}

Пусть у нас уже есть \t{radixSort(a)}, возращающий перестановку.
\begin{codep}
def getIndex(a): `\color{dkgreen}{\NO{} новая нумерация, $\O(|\t{a}| + \max_i \t{a[i]})$}`
	p = radixSort(a)
	cc = 0
	ind = [0] * n
	for i in range(n):
		cc += (i > 0 and a[p[i]] != a[p[i-1]])
		ind[p[i]] = cc
	return ind

def sufArray(s): `\color{dkgreen}{\NO{} $0 \le s_i \le \mfrac{3}{2}n$}`
	n = len(s)
	if n < 3: return slowSlowSort(s)
	s += [0, 0, 0]
	w = getIndex( [(s[i], s[i+1], s[i+2]) for i in range(n)] )
	index01 = range(0, n, 3) + range(1, n, 3) `\color{dkgreen}{\NO{} с шагом 3}`
	p01 = sufArray( [w[i] for i in index01] )
	pos = [0] * n
	for i in range(len(p01)): pos[index01[p01[i]]] = i `\color{dkgreen}{\NO{} позиция 01-суффикса в p01}`
	index2 = range(2, n, 3)
	p2 = getIndex( [(w[i], pos[i+1]) for i in index2] )
	def less(i, j): `\color{dkgreen}{\NO{} i mod 3 = 0/1, j mod 3 = 2}`
		if i mod 3 == 1: return (s[i],pos[i+1]) < (s[j],pos[j+1])
		else: return (s[i],s[i+1],pos[i+2]) < (s[j],s[j+1],pos[j+2])
	return merge(p01 `$\circ$` index01, p2 `$\circ$` index2, less) `\color{dkgreen}{\NO{} $\circ$ -- композиция: index01[p01[i]], ...}`
\end{codep}
Для $n \ge 3$ рекурсивный вызов делается от строго меньшей строки: \\
$3 \to 1{+}1,\ 4 \to 2{+}1,\ 5 \to 2{+}2,\ \dots$. 

\down
Неравенством $s_i \le \mfrac{3}{2}n$ мы в явном виде в коде нигде не пользуемся. \\
Оно нужно, чтобы гарантировать, что \t{radixSort} работает за $\O(n)$.

% \pagebreak
% \vspace*{-1.5em}
\Subsection{Быстрый поиск строки в тексте}\label{sec@sufarraysearch}

Представим себе простой бинпоиск за $\O(|s| \log(|text|))$.
Будем стараться максимально переиспользовать информацию, полученную из уже сделанных сравнений.

\down
Для краткости $\forall k$ обозначим $k$-й суффикс (\t{text[p$_k$:]}) как просто $k$.\\
{\bf Инвариант:} бинпоиск в состоянии $[l, r]$ уже знает $lcp(s, l)$ и $lcp(s, r)$.\\
Сейчас мы хотим найти $lcp(s, m)$ и перейти к $[l, m]$ или $[m, r$].\\
Заметим, $lcp(s, m) \geq max\{min\{lcp(s, l), lcp(l, m)\}, min\{lcp(s, r), lcp(r, m)\}\} = x$.\\
Мы умеем искать $lcp(l, m)$ и $lcp(r, m)$ за $\O(1) \SO$
\t{for\,($\,lcp(s, m) = x$; можем; $lcp(s,m)$++)}.

\down
Кстати, $lcp(l, m)$ и $lcp(r, m)$ не обязательно считать Фарах-Колтоном-Бендером, так как, \\
аргументы $lcp$ -- не произвольный отрезок, а вершина дерева отрезков (состояние бинпоиска).\\
Предподсчитаем $lcp$ для всех $\le 2|text|$ вершин и по ходу бинпоиска будем спускаться по Д.О.

\begin{Thm}Суммарное число увеличений на один $lcp(s, ?)$ не более $|x|$\end{Thm}
\begin{proof}
Сейчас бинпоиск в состоянии $l_i, m_i, r_i$. Следующее состояние: $l_{i+1}, r_{i+1}$.\\
Предположим, $lcp(s, l_i) \ge lcp(s, r_i)$.
Будем следить за величиной $z_i = \max\{lcp(s, l_i), lcp(s, r_i)\}$.\\
Пусть $lcp(s, m_i) < z_i \SO lcp(s, m) = x \wedge l_{i+1} = l_i \SO z_{i+1} = z_i$.
Иначе $x = z_i \wedge z_{i+1} = lcp(s,m_i)$.
\end{proof}
