\documentclass[12pt]{exam}

\usepackage[utf8]{inputenc}  % For UTF8 source encoding.
\usepackage{amsmath}  % For displaying math equations.
\usepackage{amsfonts} % For mathematical fonts (like \mathbb{E}!).
\usepackage{upgreek}  % For upright Greek letters, such as \upvarphi.
\usepackage{wasysym}  % For additional glyphs (like \smiley!).
% For document margins.
\usepackage[left=.8in, right=.8in, top=1in, bottom=1in]{geometry}
\usepackage{lastpage} % For a reference to the number of pages.

% TODO: Enter your name(s) here :)
\newcommand*{\authorname}{[Your name goes here]}

\newcommand*{\psetnumber}{2}
\newcommand*{\psetdescription}{String Data Structures}
\newcommand*{\duedate}{Tuesday, April 28th}
\newcommand*{\duetime}{2:30 PM Pacific}

% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2020}{Individual Assessment \psetnumber\\\psetdescription}{Due: \duedate\\at \duetime}
\runningheader{CS166}{Individual Assessment \psetnumber}{\authorname}
\footer{}{\footnotesize{Page \thepage\ of \pageref{LastPage}}}{}

% Exam questions.
\newcommand{\Q}[1]{\question{\large{\textbf{#1}}}}
\qformat{}  % Remove formatting from exam questions.

% Useful macro commands.
\newcommand*{\ex}{\mathbb{E}}
\newcommand*{\bigtheta}[1]{\Theta\left( #1 \right)}
\newcommand*{\bigo}[1]{O \left( #1 \right)}
\newcommand*{\bigomega}[1]{\Omega \left( #1 \right)}
\newcommand*{\prob}[1]{\text{Pr} \left[ #1 \right]}
\newcommand*{\var}[1]{\text{Var} \left[ #1 \right]}

% Custom formatting for problem parts.
\renewcommand{\thepartno}{\roman{partno}}
\renewcommand{\partlabel}{\thepartno.}

% Framed answers.
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{\fill}
\vspace{#1}
\end{framed}}

% MZ
\makeatletter
\@namedef{ver@framed.sty}{9999/12/31}
\@namedef{opt@framed.sty}{}
\makeatother
\usepackage{minted}

\printanswers

\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}

\begin{document}
\title{CS166 Individual Assessment \psetnumber: \psetdescription}
\author{\authorname}
\date{}
\maketitle
\thispagestyle{headandfoot}

\begin{questions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Q{Problem One: The Anatomy of Suffix Trees}

Consider the following paragraph, which is taken from an English translation of the excellent short story ``Before the Law'' by Franz Kafka:

\begin{center}
\begin{minipage}{0.9\textwidth}
\texttt{Before the law sits a gatekeeper. To this gatekeeper comes a man from the country who asks to gain entry into the law. But the gatekeeper says that he cannot grant him entry at the moment. The man thinks about it and then asks if he will be allowed to come in later on. "It is possible," says the gatekeeper, "but not now."}
\end{minipage}
\end{center}

Actually building a suffix tree for this text, by hand, would be quite challenging. But even without doing so, you can still infer much about what it would look like.

\begin{parts}

\part Without building a suffix tree or suffix array for the above text, determine whether the suffix tree for this passage contains a node labeled with the string "\texttt{moment}". Briefly justify your answer.

\begin{solution}
Your solution goes here!
\end{solution}

%%%%%%%%%%%%

\part Repeat the above exercise for the string "\texttt{man}".

\begin{solution}
Your solution goes here!
\end{solution}

%%%%%%%%%%%%

\part Repeat the above exercise for the string "\texttt{gatekeeper}".

\begin{solution}
Your solution goes here!
\end{solution}

\end{parts}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Q{Problem Two: Longest $\mathbf{k}$-Repeated Substrings }

Design an O$(m)$-time algorithm that, given a string $T$ of length $m$ and a positive integer $k$, returns the longest substring that appears in $T$ in at least $k$ different places. The substrings are allowed to overlap with one another; for example, given the string \texttt{HAHAHAHAHA} and $k = 3$, you'd return \texttt{HAHAHA}.

As a note, the runtime of O$(m)$ is independent of $k$. For full credit, your solution use should not use suffix trees, though you're welcome to use any other data structures you'd like.

\begin{solution}
Your solution goes here!
\end{solution}


\end{questions}
\end{document}
