Напиши пожалуйста отчёт по лабораторной работе в формате Latex. Блоки Метод решения и Описание программы должны быть очень подробными, полно и грамотно описывать суть алгоритма. В задаче использован алгоритм Укконена, который использует суффиксное дерево. Напиши больше про то, как суффиксное дерево строится за линейное время: про суффиксные ссылки, продление, живые рёбра и т.д. Также объясни потом как применяется алгоритм для поиска LCS. В Описании программы также нужно подробно описать каждую функцию в классе суффиксного дерева.

Условие:
Найти самую длинную общую подстроку двух строк с использованием суфф. дерева.

# Формат ввода
Две строки.

# Формат вывода
На первой строке нужно распечатать длину максимальной общей подстроки, затем перечислить все возможные варианты общих подстрок этой длины в порядке лексикографического возрастания без повторов.

Пример
Ввод:
xabay
xabcbay
Вывод
bay
xab

Решение
#include <iostream>

#include <vector>
#include <map>
#include <string>
#include <memory>
#include <algorithm>

typedef long long ll;

struct TSuffixTreeNode {
    std::map<char, TSuffixTreeNode *> Edges;
    TSuffixTreeNode *SuffixLink;
    ll Start;
    std::shared_ptr<ll> End;
    ll SuffixIndex = -1;

    ~TSuffixTreeNode();
};

typedef struct TSuffixTreeNode TNode;

struct TSuffixTree {
    std::string text;
    TNode *root = nullptr;

    TNode *last_new_node = nullptr;
    TNode *active_node = nullptr;

    ll active_edge = -1;
    ll active_length = 0;

    ll remaining_suffix_count = 0;
    std::shared_ptr<ll> leaf_end = std::make_shared<ll>(-1);
    ll size = -1;
    ll size1 = 0;
    ll length_of_lcs = 0;

    TSuffixTree(std::string &text, ll size);

    void PrintLCS();

    TNode *NewNode(ll start, std::shared_ptr<ll> end) const;

    void Build();

    ll EdgeLength(const TNode *n) const;

    ll WalkDown(TNode *currTNode);

    void Extend(ll pos);

    void SetSuffixIndexByDFS(TNode *n, ll labelHeight);

    ll DoTraversal(TNode *n, ll labelHeight, ll *maxHeight, std::vector<int> &substringStartIndex);

    ~TSuffixTree();
};

TSuffixTreeNode::~TSuffixTreeNode() {
    for (std::pair<char, TSuffixTreeNode *> node: Edges) {
        delete node.second;
    }
}

TSuffixTree::TSuffixTree(std::string &text, long long size) {
    this->text = text;
    size1 = size;
    Build();
    SetSuffixIndexByDFS(root, 0);
}

void TSuffixTree::PrintLCS() {
    std::vector<int> substringStartIndex;
    DoTraversal(root, 0, &length_of_lcs, substringStartIndex);

    std::cout << length_of_lcs << "\n";
    std::vector<std::string> ans;
    std::string temp;
    for (int i = 0; i < substringStartIndex.size(); ++i) {
        int k = 0;
        temp.clear();
        for (k = 0; k < length_of_lcs; k++) {
            temp += text[k + substringStartIndex[i]];
        }
        ans.push_back(temp);
    }
    std::sort(ans.begin(), ans.end());
    for (const auto &i: ans) {
        std::cout << i << "\n";
    }
}


void TSuffixTree::Build() {
    size = text.size();
    root = NewNode(-1, std::make_shared<long long>(-1));
    active_node = root;
    for (long long i = 0; i < size; i++) {
        Extend(i);
    }
}

TNode *TSuffixTree::NewNode(const long long start, std::shared_ptr<long long> End) const {
    auto *TNode = new TSuffixTreeNode;

    TNode->SuffixLink = root;
    TNode->Start = start;
    TNode->End = End;
    return TNode;
}

long long TSuffixTree::EdgeLength(const TNode *n) const {
    if (n == root) {
        return 0;
    }
    return *(n->End) - (n->Start) + 1;
}

long long TSuffixTree::WalkDown(TNode *currTNode) {
    if (active_length >= EdgeLength(currTNode)) {
        active_edge += EdgeLength(currTNode);
        active_length -= EdgeLength(currTNode);
        active_node = currTNode;
        return 1;
    }
    return 0;
}

void TSuffixTree::Extend(const long long pos) {
    ++*leaf_end;
    remaining_suffix_count++;
    last_new_node = nullptr;

    while (remaining_suffix_count > 0) {
        if (active_length == 0) {
            active_edge = pos;
        }

        if (!active_node->Edges[text[active_edge]]) {
            active_node->Edges[text[active_edge]] = NewNode(pos, leaf_end);
            if (last_new_node != nullptr) {
                last_new_node->SuffixLink = active_node;
                last_new_node = nullptr;
            }
        } else {
            TNode *next = active_node->Edges[text[active_edge]];
            if (WalkDown(next)) {
                continue;
            }

            if (text[next->Start + active_length] == text[pos]) {
                if (last_new_node != nullptr && active_node != root) {
                    last_new_node->SuffixLink = active_node;
                    last_new_node = nullptr;
                }
                active_length++;
                break;
            }

            long long splitEnd = next->Start + active_length - 1;
            TNode *split = NewNode(next->Start, std::make_shared<long long>(splitEnd));
            active_node->Edges[text[active_edge]] = split;

            split->Edges[text[pos]] = NewNode(pos, leaf_end);
            next->Start += active_length;
            split->Edges[text[next->Start]] = next;

            if (last_new_node != nullptr) {
                last_new_node->SuffixLink = split;
            }

            last_new_node = split;
        }

        remaining_suffix_count--;
        if (active_node == root && active_length > 0) {
            active_length--;
            active_edge = pos - remaining_suffix_count + 1;
        } else if (active_node != root) {
            active_node = active_node->SuffixLink;
        }
    }
}

void TSuffixTree::SetSuffixIndexByDFS(TNode *n, long long labelHeight) {
    if (n == nullptr) {
        return;
    }

    long long leaf = 1;
    for (auto child: n->Edges) {
        leaf = 0;
        SetSuffixIndexByDFS(child.second, labelHeight + EdgeLength(child.second));
    }
    if (leaf == 1) {
        n->SuffixIndex = size - labelHeight;
    }
}

long long TSuffixTree::DoTraversal(TNode *n, long long labelHeight, long long *maxHeight,
                                   std::vector<int> &substringStartIndex) {
    if (n == nullptr) {
        return 0;
    }
    long long ret = -1;
    if (n->SuffixIndex < 0) {
        for (auto child: n->Edges) {
            ret = DoTraversal(child.second, labelHeight + EdgeLength(child.second), maxHeight, substringStartIndex);
            if (n->SuffixIndex == -1) {
                n->SuffixIndex = ret;
            } else if ((n->SuffixIndex == -2 && ret == -3) || (n->SuffixIndex == -3 && ret == -2) || n->SuffixIndex == -
                       4 || ret == -4) {
                n->SuffixIndex = -4;
                if (*maxHeight < labelHeight) {
                    *maxHeight = labelHeight;
                    substringStartIndex.clear();
                    substringStartIndex.push_back(*(n->End) - labelHeight + 1);
                } else if (*maxHeight == labelHeight && !substringStartIndex.empty() && substringStartIndex.back() != *(
                               n->End) - labelHeight + 1) {
                    substringStartIndex.push_back(*(n->End) - labelHeight + 1);
                }
            }
        }
    } else if (n->SuffixIndex > -1 && n->SuffixIndex < size1) {
        return -2;
    } else if (n->SuffixIndex >= size1) {
        return -3;
    }
    return n->SuffixIndex;
}

TSuffixTree::~TSuffixTree() {
    delete root;
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::string s1, s2;
    std::cin >> s1 >> s2;
    s1 += "#";
    s2 += "$";
    std::string text = s1 + s2;
    TSuffixTree tree(text, s1.size());
    tree.PrintLCS();

    return 0;
}

Вот пример-шаблон отчёта:
\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{geometry}
\geometry{a4paper, margin=1in}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{float}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\usepackage{titlesec}
\titlespacing*{\subsubsection}{0pt}{0.1\baselineskip}{0.2\baselineskip}


\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}

\lstset{style=mystyle}

\begin{document}

\section*{Лабораторная работа №\,7 по курсу дискрeтного анализа: Жадные алгоритмы}

Выполнил студент группы М8О-309Б-22 МАИ \textit{Федоров Алексей}.

\subsection*{Условие}
Заданы $N$ объектов с ограничениями на расположение вида «$A$ должен находиться перед $B$». Необходимо найти такой порядок расположения объектов, что все ограничения выполняются.

\subsubsection*{Формат ввода}
\begin{itemize}
    \item На первой строке два числа $N$ и $M$ — количество объектов и ограничений соответственно.
    \item Далее следуют $M$ строк с ограничениями вида «$A$ $B$» ($1 \leqslant A, B \leqslant N$).
\end{itemize}

\subsubsection*{Формат вывода}
$\-1$ если расположить объекты в соответствии с требованиями невозможно, последовательность номеров объектов в противном случае.

\subsubsection*{Пример}
Ввод:
\begin{verbatim}
3 2
1 2
2 3
\end{verbatim}
Вывод:
\begin{verbatim}
1 2
2 3
\end{verbatim}

\subsection*{Метод решения}
Для решения задачи используется алгоритм топологической сортировки на основе подсчёта входящих рёбер:

\begin{enumerate}
    \item Строится граф в виде списка смежности, а также массив входящих степеней для каждой вершины.
    \item Находим все вершины с нулевой входящей степенью и добавляем их в очередь.
    \item Пока очередь не пуста:
    \begin{enumerate}
        \item Извлекаем вершину из очереди и добавляем её в результат.
        \item Уменьшаем степень входа всех соседей на $1$.
        \item Если у какой-либо вершины входящая степень стала равной $0$, добавляем её в очередь.
    \end{enumerate}
    \item Если количество обработанных вершин меньше $N$, то цикл обнаружен и решения нет. Иначе выводим ответ.
\end{enumerate}

\lstinputlisting[language=C++, caption=Реализация программы]{solution.cpp}

\section*{Описание программы}
Программа считывает входные данные, формирует список смежности и использует описанный выше алгоритм топологической сортировки для поиска ответа.

\textbf{Итоговая асимптотика:}
Алгоритм имеет сложность \(O(N + M)\), где \(N\) — количество вершин в графе, \(M\) — количество рёбер.

\section*{Тест производительности}
Результаты теста производительности представлены на графике. Мы можем заметить линейную зависимость (согласно асимптотике алгоритма).

\begin{figure}[H]
    \centering
    \includegraphics[width=1\linewidth]{graph1.png}
    \caption{Тест производительности (логарифмическая шкала)}
    \label{fig:enter-label}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=1\linewidth]{graph2.png}
    \caption{Тест производительности (обычная шкала)}
    \label{fig:enter-label}
\end{figure}

\section*{Выводы}
В ходе работы я познакомился с топологической сортировкой. Алгоритм показался несложным в реализации, а также я узнал, что применяется он, например, при создании параллельных алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно.

Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов. Также применяется при обработке исходного кода программы в некоторых компиляторах и IDE, где строится граф зависимостей между сущностями, после чего они инициализируются в нужном порядке, либо выдается ошибка о циклической зависимости.

\end{document}