\Section{Применение хешей}{27 апреля}{Жидков Николай}

\Subsection{Алгоритм Рабина-Карпа}

Постановка задачи: нам даны две строки $s,t$, надо найти все вхождения строки $s$ в строку $t$.

Посчитаем хеш от строки $s$,  обозначим его за $hash_s$. 
Заметим, что для этого вычисления нам не нужна дополнительная память, нам хватит одной переменной $hash_s$, 
в которой будет хранится хеш-функция текущего префикса строки $s$ (фактически, мы будем считать хеш как обычно, но так как для пересчета хеша нам нужно лишь значения предыдущего префикса, мы и будем хранить только хеш-функцию предущего префикса). 
Чтобы подсчитать хеш следующего префикса, надо сделать $hash_s=hash_s \cdot p + s[i]$. В конце в $hash_s$ будет лежать хеш самого длинного префикса, то есть строки $s$.

Теперь для каждой подстроки $t$ длины $|s|$ надо проверить, не совпадает ли она с $s$. 
Надо понять, как по массиву хешей префиксов вычислять хеш от подстроки.
Пусть $hast_t[i]=hash(t[0..i))$.
Тогда утверждается, что $hash_t([l, r))=hash_t[r]-hash_t[l] \cdot p^{r-l}$.
Доказательство: $hash_t([l,r))=p^{r-l-1}s[l]+p^{r-l-2}s[l+1]+...+s[r-1]=(p^{r-1}s[0]+p^{r-2}s[1]+...+s[r-1])-(p^{r-1}s[0]+...+p^{r-l}s[l-1]=
hash_t[r]-p^{r-l}(p^{l-1}s[0]+p^{l-2}s[1]+...+s[l-1])=hash_t[r]-p^{r-l}hast_t[l]$.
Поэтому решение получается простое: мы насчитываем хеши префиксов как обычно (массив $hash_t$), а потом за $O(|t|)$ перебираем подстроку $t$, имеющую длину $s$, берем ее хеш за $O(1)$ и сравниваем с $hash_s$.
Чтобы считать хеш за $O(1)$ надо еще в начале насчиать массив степеней $p$ за линию.
Итого, сейчас мы получили время $O(|s|+|t|)$.

Замечание.

В коде лучше сделать функцию $substr(l,r)$, возвращающую хеш подстроки. 
Ее тело очень простое:
\begin{code}
int substr(int l, int r) {
	return ((hash[r] - hash[l] * p[r-l]) % MOD + MOD) % MOD;
}
\end{code}
Важно помнить, что отрциательное число, взятое по модулю, не обязательно станет неотрицательным. 
Поэтому поcле $(hash[r] - hash[l] \cdot p[r - l]) \% MOD$ мы могли получить отрицательное число. 
Я добавил к результату $MOD$, чтобы он стал точно положительным, и снова взял по модулю.
Так работает дольше из-за двух взятий по модулю, от второго можно избавиться, заменим взятие на проверку ($if (x \geqslant MOD) then$ $x -= MOD$).
Также если вы постоянно сравниваете подстроки с помощью вызовов функции $substr$, есть смысл завести отдельную функцию для сравенения.
\begin{code}
bool equal(int l1, int r1, int l2, int r2) {
	return (r1 - l1 == r2 - l2 && ((hash[r1]-hash[l1]*p[r1-l1])-(hash[r2]-hash[l2]*p[r2-l2])) % MOD == 0);
}
\end{code}
Такой код делает одно взятие по модулю вместо двух.

Замечание.

Алгоритм Рабина-Карпа можно писать с $O(1)$ дополнительной памяти (то есть, кроме строк $s$, $t$ ничего не хранить).
Мы уже умеем считать $hash_s$.
Так же посчиатем $hash_t([0..|s|))$.
Теперь заметим, что мы можем за $O(1)$ пересчитать $hash_t([i+1..i+1+|s|))$, зная $hash_t([i..i+|s|))$.
Выведем формулу: $hash_t([i+1..i+1+|s|))=p^{|s|-1}t[i+1]+p^{|s|-2}t[i+2]+..+t[i+|s|]=p(p^{|s|-1}t[i]+p^{|s|-2}t[i+1]+..t[i+|s|-1])+t[i+|s|]-p^{|s|}t[i]=
p\cdot hash_t([i..i+|s|))+t[i+|s|]-p^{|s|}t[i]$.
Заметим, что $p^{|s|}$ мы можем один раз насчитать в начале программы без дополнительной памяти.
Итого, алгорим такой: считаем хеш от первой подстроки, а дальше двигаем "окошко" длины $|s|$, пересчитывая хеш окошка за $O(1)$, выкидываю первый символ "окошка" и добавляя новый.


\Subsection{Сравение строк, LCP}

Пусть нам даны строки $s$, $t$ с уже насчитанными хешами на префиксах.
Мы хотим за $O(\log(min(|s|, |t|)))$ понять, какая строчка лексикографически меньше.
Для решения заметим, что у строк $s$, $t$ есть максимальный общий префикс длины $k$ (он обозначается $LCP(s, t)$ (Largest Common Prefix)), а в следующем символе они уже отличаются, поэтому если мы найдем $k$, то дальше мы за $O(1)$ поймем, какая из строк меньше $s < t \leftrightarrow s[k]<t[k]$.
Если у строк есть общий префикс длины $k$, то префиксы длины $\leqslant k$ у строк $s, t$ тоже равны, а если длины $k$, а если нет длины $k$, то и большей нет. 
Это означает, что $k$ можно найти бинпоиском.
Мы проверяем, что $s[0..\frac{l+r}{2}]=t[0..\frac{l+r}{2}]$ с помощью  хешей (мы уже научились за $O(1)$ брать хеш подстроки). 
Если строки равны, то двигае левый указатель, иначе двигаем правый.
Теперь мы умеем находить наибольшой общий префикс двух строк, а также сравнивать их на больше-меньше.

Замечание.
Заметим, что кроме строк $s$, $t$, мы можем сравнить и любые их две подстроки за $O(\log(min(|s|,|t|)))$.
Для этого надо делать так же бинпоиск по длине общего префикса и проверять, что $s[l..l+k]=t[r..r+k]$ с помощью хешей подстрок.

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

Нам дана строчка $s$. 
Мы хотим отсортировать все ее суффиксы в лексикографическом порядке.
Каждый суффикс однозначано задается позицией в $s$ своего первого символа, поэтому на выходе мы хотим получить перестановку чисел от $1$ до $n$ - отсортированные суффиксы.

Решение 1.
Отсортируем все суффиксы с помощью $std::sort$, где компаратор будет просто сравнивать суффиксы за $O(n)$ (то есть просто проходим по строкам до первого несовпадения).
Решение работает за $O(n^2\log n)$, так как мы делаем $O(n\log n)$ сравнений строк, каждое работает за $O(n)$.

Решение 2.
Отсортируем все суффиксы с помощью $std::sort$, где компаратор будет сравнивать суффиксы за $O(\log n)$ (мы учились это делать хешами чуть выше).
Такое решение работает уже за $O(n\log^2 n)$.
Заметим, что мы используем линейное количество дополнительной памяти (один массив хешей префиксов строки $s$).

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

Нам дана строка $t$, и приходят запросы $s_i$ и надо ответить, является ли $s_i$ подстрокой $t$.

Построим суффиксный массив строки $t$.
Легко видеть, что строка $s_i$, если входит в $t$, является началом какого-то суффикса.
Далее заметим, что в суффиксом массиве сначала лежат все суффиксы, меньшие или равные $s$, а потом большие $s$ (так как все суффиксы отсортированны).
Поэтому можно найти эту границу бинарным поиском (пусть $k$ - последний суффикс, который меньше или равен $s$), а потом проверить, что $t[k..k+|s|)=s$ за один проход (достаточно проверить только $k$, так как если этот префикс длины $|s|$ этого суффикса не равен $s$, то и у любой более высокой в суффиксном массиве строки он тоже не равен (так как эти строки только меньше, чем $k$)).
Как найти границу? Пусть в бинпоиске мы стоим в суффиксе $m$.
Нам надо проверить, больше он $s_i$ или нет.
Это можно сделать за линейное время обычным сравением (и получить $O(|s_i|+\log |t| \cdot |s_i|)$), а можно за $O(\log n)$ с помощью хешей (для этого надо их насчитать один раз для $t$ и для каждого $s_i$) и получить $O(|s_i|+\log |t| \cdot \log |s_i|)$.
В обеих асимптотиках учитывается $|s_i|$ - считывание строки, вычисление хешей префиксов, финальное сравнение, $\log |t|$ на бинпоиск, и еще что-то на сравнение строк ($|s_i|$ в первом случае и $|\log s_i|$ во втором).

\Subsection{Наибольшая общая подстрока двух строк}

Даны две строки $s$, $t$, необходимо найти их наибольшую общую подстроку.
Заметим, что если у них есть общая подстрока длины $k$, то есть и любой меньшей длины, а если нет длины $k$? то и большей нет.
Поэтому будем делать бинпоиск по длине $k$.
Как проверить, что у строк есть равные строки длины $k$?
Посчитаем хеши все подстрок $s$ длины $k$ (делаем это как в алгоритме Рабина-Карпа, например) и сложим их в хеш-таблицу.
Теперь идем по строке $t$, берем очередную подстроку длины $k$ и проверяем, нет ли ее в хеш-таблице.
Если есть, значит, мы нашли общую подстроку длины $k$.
Все, что внутри бинпоиска, работает за линейное время (подсчитать хеши подстрок одной и той же длины можно за линию как в Рабине-Карпе, а хеш-таблица состоит из $O(|s|)$ элементов и мы делаем к ней $O(|t|)$ запросов, поэтому работает за $O(|s|+|t|)$), следовательно, суммарно получаем $O(\log(min(|s|, |t|)(|s|+|t|))$.


