Letter Sequence Analysis

Time limit1sMemory limit128 MB

Summary
Read a text block to EOF and, for each sequence length 1 to 5, list the five most frequent letter sequences with alphabetized ties.
Level

Medium4 of 10

Topics
String, Hash map, Sorting, Implementation
Solved
No attempts yet

Problem

Cryptographic analysis relies heavily on how often individual letters and letter sequences appear in a language. For English text, for example, knowing that E, L, N, R, S, and T are among the most common letters — and knowing the most common letter pairs, triplets, and so on — reveals a great deal about an encrypted message.

Write a program that reads a block of text and performs letter-sequence analysis on it. For every sequence length from 1 to 5, report the sequences that occur with the five highest frequencies: the single characters with the five highest frequencies, the character pairs with the five highest frequencies, and so on up to sequences of five characters.

Only consider contiguous runs of alphabetic characters, and ignore case (so a and A are the same letter). A sequence of length LL is any run of LL consecutive letters that lies entirely within one such alphabetic run; a sequence never crosses a non-letter character.

Input

The input is a single block of text of arbitrary length that may span several lines. Read it until end of file. It may contain letters, digits, punctuation, and whitespace.

Output

Print one section for each sequence length from 1 to 5. Each section starts with the header line

Analysis for Letter Sequences of Length L

followed by a line of dashes (-) as long as the header (41 dashes). Then, for that length, print the frequencies in descending order, using at most the five highest distinct frequencies. For each such frequency print

Frequency = F, Sequence(s) = (S1,S2,...)

where S1, S2, … are all sequences that occur exactly FF times, written in upper case, separated by commas with no spaces, and listed in alphabetical order. If a length has fewer than five distinct frequencies, print only as many as exist (possibly none). Separate consecutive length sections with a single blank line.

Examples1

  1. Example 1

    Input
    Peter Piper Picks Pickles!
    Expected output
    Analysis for Letter Sequences of Length 1
-----------------------------------------
Frequency = 5, Sequence(s) = (P)
Frequency = 4, Sequence(s) = (E)
Frequency = 3, Sequence(s) = (I)
Frequency = 2, Sequence(s) = (C,K,R,S)
Frequency = 1, Sequence(s) = (L,T)

Analysis for Letter Sequences of Length 2
-----------------------------------------
Frequency = 3, Sequence(s) = (PI)
Frequency = 2, Sequence(s) = (CK,ER,IC,PE)
Frequency = 1, Sequence(s) = (ES,ET,IP,KL,KS,LE,TE)

Analysis for Letter Sequences of Length 3
-----------------------------------------
Frequency = 2, Sequence(s) = (ICK,PIC)
Frequency = 1, Sequence(s) = (CKL,CKS,ETE,IPE,KLE,LES,PER,PET,PIP,TER)

Analysis for Letter Sequences of Length 4
-----------------------------------------
Frequency = 2, Sequence(s) = (PICK)
Frequency = 1, Sequence(s) = (CKLE,ETER,ICKL,ICKS,IPER,KLES,PETE,PIPE)

Analysis for Letter Sequences of Length 5
-----------------------------------------
Frequency = 1, Sequence(s) = (CKLES,ICKLE,PETER,PICKL,PICKS,PIPER)