Descrição
Uma cadeia ponderada é definida sobre um alfabeto Σ e uma função f que atribui um peso a cada caractere do alfabeto. Assim, podemos definir o peso de uma cadeia s como a soma dos pesos de todos os caracteres em s.
Vários problemas da bioinformática podem ser formalizados como problemas em cadeias ponderadas. Um exemplo é a espectrometria de massa de proteı́nas, uma técnica que permite identificar proteı́nas de forma bastante eficiente. Podemos representar cada aminoácido por um caractere distinto e uma proteı́na é representada pela cadeia de caracteres relativos aos aminoácidos que a compõe.
Uma das aplicações da espectrometria de massa de proteı́nas são buscas em bancos de dados. Para isso a cadeia que representa a proteina é dividida em subcadeias, a massa de cada subcadeia é determinada, e a lista de massas é comparada com um banco de dados de proteı́nas. Um dos desafios para essa técnica é lidar com cadeias muito grandes de caracteres, que podem ter várias possı́veis subcadeias. A quantidade de subcadeias selecionadas é fundamental para obter bons resultados.
Em seu primeiro dia de estágio em um renomado laboratório de biotecnologia, Carlos recebeu a tarefa de determinar, para uma cadeia s, a quantidade de pesos distintos encontrada ao avaliar os pesos de todas as subcadeias não vazias de caracteres consecutivos de s.
Carlos não conseguiu pensar em uma solução eficiente para essa tarefa, mas felizmente ele conhece o grupo ideal para auxiliá-lo.
Considerando que s é formada por letras minúsculas e cada letra tem um peso diferente entre 1 e 26: a letra a tem peso 1, a letra b tem peso 2 e assim por diante. Mostre que seu time é capaz de ajudar Carlos a impressionar seu supervisor logo na primeira semana, com uma solução capaz de lidar facilmente com as maiores cadeias de caracteres existentes.
Entrada
Apenas uma linha, que contém a cadeia s formada por letras minúsculas, cujo comprimento |s| satisfaz 1 ≤ |s| ≤ 105.
Saída
Seu programa deve produzir uma única linha com um inteiro representando a quantidade de pesos distintos das subcadeias não vazias de caracteres consecutivos de s.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
adbbabdcdbcbacdabbaccdac |
56
|
|
abbab |
8 |
Efetue Login ou Cadastre-se para submeter uma solução.
Competição: Maratona de Programação da SBC 2017