%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% D1 de MAC323 Estruturas de Dados                                   %
% BCC, 1o. semestre de 2001                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 16 Apr 2002 12:46:06am BRT yoshi@ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

\let\:=\colon
\def\dist{\mathop{\rm dist}\nolimits}
\def\RR{\mathbb R}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}

\begin{document}
%\title[MAC323 Estruturas de Dados]{{\small Primeiro Exercício-Programa}\\
%\vspace{1\jot}{\tiny BCC, Primeiro Semestre de de 2001}\\
%\vspace{3\jot}} 

\title[MAC323, 1o.~Desafio, Repetições]%
{{\footnotesize MAC323/BCC Primeiro Desafio}\\
\vspace{6\jot}
\textsl{Segmentos Repetidos em Textos}}
\author{Y.\ Kohayakawa}
\date{Versão de \today}
\maketitle
\thispagestyle{empty}

Escreva um programa que recebe um texto como entrada e devolve o trecho
repetido mais comprido neste texto.  Por exemplo, se o texto de entrada for
{\footnotesize
\begin{verbatim}
    3.14159265358979323846264338327950288419716939937510582097
    94459230781640628620899862803482534211706798214808651328230
    6647093844609550582231725359408128481117450284102701938521105
    5596446229489549303819644288109756659334461284756482337867831
    65271201909145648566923460348610454326648213393607260249141273
    7245870066...
\end{verbatim}
  }
\noindent então a saída de seu programa deve ser \texttt{0348}.  No
\href{ftp://ibiblio.org/pub/docs/books/gutenberg/etext92/bible11.txt}{\textit{King
    James' Bible}} do \href{http://promo.net/pg/}{Projeto Gutenberg}
(removendo os números dos versos e ignorando quebras de linha), temos o
seguinte texto repetido: {\footnotesize
\begin{verbatim}
  , offered: His offering was one silver charger, the weight whereof was an
  hundred and thirty shekels, one silver bowl of seventy shekels, after the
  shekel of the sanctuary; both of them full of fine flour mingled with oil
  for a meat offering: One golden spoon of ten shekels, full of incense: One
  young bullock, one ram, one lamb of the first year, for a burnt offering:
  One kid of the goats for a sin offering: And for a sacrifice of peace
  offerings, two oxen, five rams, five he goats, five lambs of the first year:
  this was the offering of Ahi
\end{verbatim}
  }\noindent onde quebramos em linhas para facilitar a apresentação.  (O
\href{http://www.ime.usp.br/~yoshi/2001i/mac323/Desafios/Repeticoes/bible11d.txt}{arquivo
  processado} tem~4138299 caracteres.)

Você deve tentar descobrir boas estruturas de dados para escrever um programa
eficiente para resolver este problema.  Pense inicialmente sem consultar
nenhuma bibliografia.

\subsection*{Uma solução}  Para uma solucação para este desafio, consulte o
livro \href{http://www.programmingpearls.com/}{Programming Pearls}, de
\href{http://www.cs.bell-labs.com/who/jlb/index.html}{Jon Bentley}.

\subsection*{O desafio}
O desafio é você escrever um programa mais eficiente do que aquele em 
\href{http://www.programmingpearls.com/}{Programming Pearls}.

É provavelmente difícil melhorar o programa de Bentley substancialmente,
embora ele seja extremamente curto e simples.  Assim, talvez uma idéia seria
você aumentar as `funcionalidades' dele.  Por exemplo, o seu programa poderia
procurar trechos repetidos que sejam `parecidos' (por exemplo, diferem apenas
em um caracter ou algo assim).

\subsection*{Avaliação}
Na avaliação de seu programa, estarei particularmente interessado em sua
eficiência, nas estruturas de dados usadas, e nas funcionalidades extras que
você colocar.

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 
