%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% EP2 de Computacao II, CCM                                          %
% 1o. semestre de 20021                                              %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 16 Apr 2002 10:55:52am BRT yoshi@erdos.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{Exercício Programa 2}
\maketitle
\thispagestyle{empty}

\noindent\textbf{Data de entrega:}\quad 9/5/2002

\bigskip

\noindent\textbf{Problema.}\quad
\textsl{Escreva um programa que recebe um texto como entrada e devolve o trecho
repetido mais comprido neste texto.}  

\bigskip\noindent
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~4169466 caracteres.)

\textit{Você deve tentar descobrir um bom algoritmo para resolver este
  problema.}  O algoritmo ingênuo, discutido em um exercício em sala, tem
comportamento pelo menos quadrático, que o torna inútil para tratar textos
longos.

Entregue não só os programas (por correio eletrônico para
\texttt{yoshi@ime.usp.br} e \texttt{daniel@linux.ime.usp.br}) como também um
relatório.  Envie seu relatório eletronicamente também.

\bigskip

\begin{enumerate}
\item Para os testes de seu programa, use entradas variadas.  O
  \href{http://promo.net/pg/}{Projeto Gutenberg} é uma boa fonte de exemplos
  (grandes).  Você também pode usar cadeias de caracteres gerados
  aleatoriamente.

\item Você pode usar o comando \texttt{time} para determinar o tempo gasto
  pelo seu programa, como no EP1.

\item Use o truque do \texttt{o} (``o pequeno'') visto em sala para contar \textit{o
  número de comparações entre caracteres} que o seu programa executa.  Use o
  \texttt{GNUPLOT} para verificar como cresce este número conforme o texto de
  entrada cresce. 

\item Explique no relatório o funcionamento do seu sistema e discuta seus
  resultados. 

\end{enumerate}
\end{document}

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