SPOJ Brasil

Um dos métodos mais antigos de cifragem de mensagens é a cifragem por subsituição. Variantes desse método têm sido usadas através dos tempos, por usuários como Julius Cæsar (100–44 a.C.) e a Rainha Mary da Escócia (1542–1587).

O método é bem simples: cada letra da mensagem é substituída por outra letra. Por exemplo, todas as letras ‘A’ do texto são substituídas por ‘X’, todas as letras ‘B’ por ‘E’, e assim por diante.

A deficiência do método de cifragem por substituição é que ele é vulnerável à análise de freqüências. Ela se baseia no fato de que, para trechos grandes de mensagens, certas letras ocorrem com freqüências que são aproximadamente as mesmas para a maioria dos trechos escritos na mesma língua. Como a mensagem foi cifrada de forma que cada letra seja substituída por uma outra, a nova letra herdará todos os atributos da letra antiga, incluindo sua freqüência. Em português, a letra mais freqüente é ‘A’. Assim, se a letra mais freqüente em uma mensagem cifrada é ‘T’, muito provavelmente ‘T’ representa a letra ‘A’ no texto original.

Embora não se saiba quem descobriu que a variação de freqüência das letras pode ser explorada para quebrar cifras, a descrição mais antiga conhecida é do cientista Abu Yusuf Ya ’qub ibn Is-haq ibn as-Sabbah ibn ómran ibn Ismail al-Kindi, que viveu no século IX. Abu Yusuf escreveu 290 livros em assuntos tão variados como medicina, astronomia, matemática, linguística e música. Mas a sua maior obra, redescoberta em 1987 nos Arquivos Otomanos Sulaimaniyyah, em Istambul, intitula-se “Um Manuscrito Sobre Como Decifrar Mensagens Criptografadas”.

A quebra da cifragem por substituição marcou o nascimento da ciência da criptologia, que tem múltiplas aplicações nos dias de hoje.

Tarefa

Sua tarefa é decifrar uma mensagem cifrada utilizando o método de substituição, dadas a mensagem cifrada e a lista de freqüências das letras em uma determinada língua.

Entrada

A entrada é composta de vários conjuntos de testes. A primeira linha de um conjunto de testes contém dois inteiros T e F, separados por um espaço em branco, que indicam respectivamente o número de caracteres do texto cifrado (1 <= T <= 10000), e o número de letras da lista de freqüências (1 <= F <= 26). A segunda linha de um caso de testes contém uma lista de F letras c1 c2 c3 ... cF utilizadas na mensagem original, em ordem decrescente da freqüencia em que elas aparecem na língua considerada (ou seja, c1 é a letra mais freqüente, cF a menos freqüente, ‘a’ <= ci <= ‘z’). A terceira linha de um caso de testes contém os T caracteres do texto cifrado. O texto cifrado contém caracteres de ‘a’ a ‘z’ e caracteres ‘ ’ (espaço em branco). O final da entrada é indicado por T = F = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato ‘Teste n’, onde ‘n’ é numerado seqüencialmente a partir de 1. A segunda linha deve conter o texto original (decifrado). A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Entrada:
15 9
aegilmqtu
ahagibf a caeda
33 13
saeontcbrpdum
kfqdt dt twdt ldtgt hft pgmkghagz
0 0

Saída:
Teste 1
ataquem a galia

Teste 2
todas as suas bases nos pertencem

1 <= T <= 10000 (T = 0 para indicar final da entrada)
1 <= F <= 26 (F = 0 para indicar o final da entrada)