Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ARQUIVO - Recuperação de arquivos

Sua escola possui um computador que é usado como um servidor web para hospedar a página da instituição, páginas pessoais, páginas de grupos de pesquisas e muitas outras coisas.

Recentemente, o disco rídigo foi corrompido, portanto a organização de todos os arquivos foi perdida. Infelizmente, não há backup da informação. A única esperança é olhar todas as informações do disco e tentar descobrir quais partes pertencem a cada arquivo. Felizmente, o disco estava usando um sistema de arquivos que guardava cada arquivo individual de forma contígua, portanto somente partes contíguas das informações devem ser inspecionadas.

As informações do disco são uma sequência de bytes. Cada byte nesse disco pode armazenar uma letra do alfabeto inglês (distinguindo entre maísculas e minúsculas), um dígito decimal, um ponto ou uma vírgula, totalizando 64 diferentes caracteres.

Enquanto você estava pensando como resolver este problema, você repentinamente lembrou que o sistema de arquivos também mantinha múltiplas cópias de cada arquivo, assim apenas partes de bytes contíguos que são repetidos possuem uma chance de ser um arquivo. Além disso, para cada repetição dos mesmos bytes contíguos, apenas uma cópia precisa ser verificada. Por exemplo, se a informação é ababcabb, as sequências contíguas a, b e ab sao repetidas, mas nada contendo c, ba nem bb é. Desta forma, temos 3 blocos de bytes contíguos que devem ser checados.

Você decidiu escrever um programa que calcula exatamente quantas sequências devem ser verificadas, ou seja, o número de sequências de bytes contíguas e distintas que aparecem ao menos duas vezes no disco rígido.

Entrada

A entrada possui vários casos de teste. Cada caso de teste é dado em exatamente uma linha contendo uma string não-vazia de no máximo 105 caracteres representando as informações no disco rígido. Cada caractere na string é uma letra minúscula, uma letra maiúscula, um dígito, um ponto ou uma vírgula.

O último caso de teste é seguido de uma linha contendo um único asterisco.

Saída

Para cada caso de teste, imprima uma única linha contendo um único inteiro, o número de subsequências contíguas distintas que aparecem ao menos duas vezes na entrada.

Exemplo

Entrada:
ababcabb
mississippi
aaaaaaaaaaaaaaaaaaaaaaaaaa
012345678,abcdefg.STUVWXYZ
say.twice,say.twice
*

Saída:
3
9
25
0
45


Adicionado por:Wanderley Guimarăes
Data:2011-03-07
Tempo limite:1.179s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programação da ACM 2009

hide comments
2022-12-28 20:20:48
deleted

Last edit: 2022-12-28 20:21:56
2022-12-28 20:20:08
deleted

Last edit: 2022-12-28 20:22:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.