Soundex Indexing

Interview

Time limit1sMemory limit512 MB

Summary

For each uppercase name, produce its Soundex code (letter plus three digits), skipping vowels and merging repeated codes, and print names and codes in fixed columns.

Level: Easy3 of 10
Topics: String, Implementation, Simulation
Solved: No attempts yet

Problem

The Soundex Index System was developed so that names that sound alike, or names with similar spelling, could be encoded for easy retrieval. The U.S. Bureau of the Census has used it, and some States use it to help encode driver's license numbers. Your task is to read a sequence of names, one at a time and one per line, compute the corresponding soundex code, and write the name and its soundex code to the output file, one line of output per name.

Names contain from 1 to 20 upper case alphabetic characters (ASCII values 65 through 90, inclusive). Names shorter than 20 characters are NOT padded with blanks. Thus a name consists of upper case letters only.

How to generate the Soundex Code:

A Soundex Code always consists of a letter followed by three digits. Here are the rules for soundex encoding:

The first letter of a name appears as the first and only letter in the soundex code.
The letters A, E, I, O, U, Y, W, and H are never encoded, but they do break successive code sequences (see the next rule).
All other letters are encoded EXCEPT when they immediately follow a letter (including the first letter) that would be encoded with the same code digit.
The soundex code guide is:

Code Key Letters and Equivalents
1 B, P, F, V
2 C, S, K, G, J, Q, X, Z
3 D, T
4 L
5 M, N
6 R
Trailing zeros are appended to short codes so all names are encoded with a letter followed by three digits.
Longer codes are truncated after the third digit.

Code	Key Letters and Equivalents
1	B, P, F, V
2	C, S, K, G, J, Q, X, Z
3	D, T
4	L
5	M, N
6	R

Input

The input contains a list of names, one per line. Each name does not exceed 20 characters, and you may assume that only upper case letters are used. Your program should continue to read names until the end of the file is detected.

Output

The output consists of a column of names and a column of their corresponding soundex codes. Write the headings "NAME" and "SOUNDEX CODE" in the first line of the output in columns 10 and 35, respectively. After the heading line, the names and soundex codes are written (one pair per line) with the name starting in column 10 and the soundex code beginning in column 35. The comment "END OF OUTPUT" should appear at the end of the output on the line immediately after the last name. This comment should be written starting in column 20.

Examples1

Example 1

Input

LEE
KUHNE
EBELL
EBELSON
SCHAEFER
SCHAAK

Expected output

         NAME                     SOUNDEX CODE
         LEE                      L000
         KUHNE                    K500
         EBELL                    E140
         EBELSON                  E142
         SCHAEFER                 S160
         SCHAAK                   S200
                   END OF OUTPUT