\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{am 26.\@ Mai 2015 vor der Vorlesung in die
Mitarbeiterschachteln}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\eps}{\varepsilon}


\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung \hfill SoSe 2015

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Lena Schlipf, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Ukkonens Algorithmus}{10 Punkte}

Betrachten Sie die Zeichenkette $S = abra\_a\_abra\$ $, wobei die zwei 
Unterstriche f\"ur die Initialen Ihres Vor- und Nachnamens stehen. 
Beschreiben Sie im Detail, wie der Suffixbaum für diesen String mit 
Ukkonens Algorithmus aufgebaut wird. Illustrieren Sie 
insbesondere die Anzahl der Skip \& Count Schritte und die $j_i$-Werte.

\AUFGABE{Suffixarrays} {10 Punkte}

Das Suffixarray $A$ für einen Text $T$, $|T|=m$, ($T$ endet mit dem Sonderzeichen \$) 
ist ein Array der Länge $m$, das die Startpositionen der lexikographisch sortierten
Suffixe von $T$ enth\"alt.

\begin{enumerate}
\item Beschreiben Sie, wie man in $O(m)$ Zeit aus einem Suffixbaum für 
  $T$ ein Suffix\-array erstellen kann.
\item Beschreiben Sie einen Algorithmus, der auf naive Weise Bin\"arsuche im 
Suffixarray $A$ zur Stringsuche von einem Muster $P$ ($|P|=n$) in $T$ verwendet und 
analysieren Sie seine Laufzeit.
\item Angenommen, für je zwei Indizes $1 \leq i<j\leq m$ sei $\text{lcp}(i,j)$ 
als L\"ange des l\"angsten gemeinsamen Pr\"afixes von $T[i,m]$ und $T[j,m]$ bekannt. Die 
Laufzeit der Bin\"arsuche l\"asst sich jetzt auf $O(n + \log m)$ verbessern. Wie?
\end{enumerate}


\AUFGABE{Maximale Palindrome}{10 Punkte}

Ein \emph{Palindrom} ist ein String $S$, der vorw\"arts und rückw\"arts gelesen gleich bleibt,
also für den gilt
$S=S^R$.

Beschreiben  Sie  einen  Algorithmus,  der  f\"ur einen  Text $T$
in  linearer Zeit alle in $T$ enthaltenen \emph{maximalen Palindrome} bestimmt.
Maximale Palindrome sind dabei Teilstrings von $T$, die Palindrom sind und die
nicht verl\"angert werden k\"onnen ohne diese Eigenschaft zu verletzten.


\end{description}
\end{document}
