MAC323/BCC PRIMEIRO DESAFIO

SEGMENTOS REPETIDOS EM TEXTOS

Y. KOHAYAKAWA

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

    3.14159265358979323846264338327950288419716939937510582097
    94459230781640628620899862803482534211706798214808651328230
    6647093844609550582231725359408128481117450284102701938521105
    5596446229489549303819644288109756659334461284756482337867831
    65271201909145648566923460348610454326648213393607260249141273
    7245870066...

então a saída de seu programa deve ser 0348. No King James’ Bible do Projeto Gutenberg (removendo os números dos versos e ignorando quebras de linha), temos o seguinte texto repetido:

  , 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

onde quebramos em linhas para facilitar a apresentação. (O 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.

Uma solução. Para uma solucação para este desafio, consulte o livro Programming Pearls, de Jon Bentley.

O desafio. O desafio é você escrever um programa mais eficiente do que aquele em 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).

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.

Date: Versão de 16 de abril de 2002.