
\Section{Строки. Поиск подстроки в строке.}{19 апреля}{Федорова Анна}

\Subsection{Обозначения}

%\vspace*{-1em}
%\begin{MyList}
%\item
   $s$, $t$ -- строки, $|s|$ -- длина строки, \\
  \t{s[l:r)} или \t{s[l:r]} -- подстрока, \\
  \t{s[0:i)} -- префикс, \t{s[i:|s|-1]} -- суффикс.\\
%\item 
  $\Sigma$ -- алфавит, $|\Sigma|$ -- размер алфавита.
%\end{MyList}
%\vspace*{-1em}

\Subsection{C++.}

В языке \t{C++} у строк типа \t{string} есть стандартный метод \t{find}. Работает за $\O(|s| \cdot |t|)$,
возвращает целое число -- номер позиции в исходной строке, начиная с которого начинается первое вхождение подстроки.

\vspace*{0.2em}
Функция из \t{<cstring>} \t{strstr(t, s)} ищет $s$ в $t$ и работает за линию под \t{Unix} и за квадрат под \t{Windows}.

\vspace*{0.2em}
В обоих случаях стоит заметить, квадрат имеет очень маленькую константу (AVX регистры).

\Subsection{КМП.}

Постановка задачи. Есть строка $t$ и образец $s$. Мы хотим приложить строку $s$ ко всем позициям строки $t$ и вернуть всё множество вхождений.
Введем понятие префикс-функции строки.
\begin{Def}
  Префикс-функция строки $s$ -- массив $p$.
  p[i] -- длина максимального собственного префикса \t{s[0:i]}, совпадающего с суффиксом \t{s[0:i]}. p[0] = 0.
\end{Def}

\THE{Алгоритм Кнута-Мориса-Пратта}.

$\NO{}$ -- любой символ, который не встречается ни в $t$, ни в $s$. 
Создадим новую строку: $s\NO{}t$ и найдем от неё префикс-функцию. Ни одно значение префикс-функции на такой строке 
не может быть больше длины строки $s$, потому что у нас используется символ $\NO{}$. 
Так же, если префикс-функция равна длине $s$, то мы нашли искомое вхождение, так как префикс длины $|s|$ в $s\NO{}t$ -- это и есть строка $s$. 

\begin{code}
p[0] = k = 0
for (i = 0; i < n; i++)
while (k > 0 && s[k] != s[i])
	k = p[k - 1]
if (s[k] == s[i])
	k++
p[i] = k
\end{code}
   
Алгоритм работает за $\O(|s|+|text|)$ (от длины конкатенации).
В приведенном коде видно, что внутри \t{while} переменная $k$ убывает, 
а после этого цикла $k$ увеличивается суммарно не более $n{-}1$ раз. При этом $k$ всегда неотрицательно.
Докажем корректность. Для этого введем несколько обозначений: 
\begin{MyList}
\item $\alpha$ -- префикс длины $p_k$, а $\alpha '$ -- суффикс.
\item $x$ -- $k + 1$-й символ.
\item $\beta = \overline{\beta} x$ -- префикс длины $p_{k + 1}$, нахождение $\overline{\beta}$ эквивалентно вычислению $p_{k + 1}$.
\end{MyList}

\vspace*{-2em}
\begin{figure}[h]
\center{\includegraphics{fedorova/card.PNG}} %[width=\linewidth]
\end{figure}
\vspace*{-2em}

\begin{Thm}
$\forall k \colon p[k + 1] \le p[k] + 1$ имеем $p[k + 1] = p[k] + 1 \Longleftrightarrow s[p_k + 1] = s[k + 1]$.
\end{Thm}
\begin{proof}

\vspace*{0em}
Если $p_{k+1} > p_k + 1$, то $|\beta| > |\alpha|$, причём $\beta$ является одновременно префиксом строки $s$ и суффиксом $s[1:k]$, что противоречит выбору $p_k$.\\
Если $s[k + 1] \ne s[p_k + 1]$, то $p_{k + 1} \le p_k$ и $\overline{\beta}$ -- собственный префикс и суффикс $\alpha$.\\
\end{proof}

\vspace*{-1em}
\Subsection{Z-функция.}

\begin{Def} $Z$-функция -- массив. $Z[0] = 0$.
$\forall i \not= 0 \colon Z[i] = LCP(s, s[i:n])$, где $LCP$ -- наибольший общий префикс, $n$ -- длина строки $s$.
\end{Def}
Для поиска подстроки, снова введем строку $s\NO{}t$ и посчитаем на ней значения $Z$-функции. 
Найдем все позиции $i$, для которых $Z[i] = |s|$, гарантируется, что это позиции всех вхождений строки $s$ в строку $t$. 
Значение $Z$-функции не может быть больше, чем $|s|$, а значения, меньшие этого нас не устраивают.
\begin{code} 
Z[0] = 0
for (i = 0; i < n; i++)
	int k = 0
	while (s[i + k] == s[k])
		k++
	Z[i] = k
\end{code}
Приведенный алгоритм работает за $\Theta(n^2)$ для строки $aaa{\dots}a$.
\begin{Lm}
Пусть $l \colon l + Z[l] = \max$ среди всех $l < i$. $r = l + Z[l]$. \\
Тогда $s[0:Z[l]) = s[l:r)$ и $s[i-l:Z[l]) = s[i:r)$.
\end{Lm}

Следствие леммы: $Z[i] \ge \min(r - i, Z[i] - l)$.

Немного модифицируем код, чтобы получить асимптотику $\O(n)$.
\begin{code} 
  Z[0] = 0, l = r = 0
  for (i = 0; i < n; i++)
  	int k = r <= i ? 0 : min(r - i, Z[i] - 1)
  	while (s[i + k] == s[k])
  		k++
  	Z[i] = k
  	if (i + k > r) l = i, r = i + k
\end{code}
\begin{Lm}
Приведенный выше алгоритм работает за $\O(n)$.
\end{Lm}
\begin{proof} Если увеличивается $k$, то увеличивается и значение $r$, а оно не может увеличиваться больше $n$ раз.\\
%Пусть позиция $l$ такова, что $Z[l] = \max$. Мы рассматриваем позицию $i$ правее. 
Пусть последний совпаший по лемме символ находится $< r$. 
У строки $i - l$ последний символ не совпал, значит, и рассматриваемый последний символ не совпадёт.
Пусть $\ge r$, тогда $i+Z[i]$ будет правее $r$ и $k$ увеличится.
\end{proof}
