Explore BrainMass

Explore BrainMass

    Shortest Prefixes

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Shortest Prefixes

    Input: Prefix .in
    Output: Prefix .out

    A prefix of a string is a substring string at the beginning of the given string. The prefixes of "carbon" are: "c", "ca", car", "carb", "carbo", and "carbon". Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, "carbohydrate "is commonly abbreviated by "carb". In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

    In the sample input below, "carbohydrate" can be abbreviated to "carboh", but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the list that begin with "carbo".

    An exact match will override a prefix match. For example, the prefix "car" matches the given word "car" exactly. Therefore, it is understood without ambiguity that "car" is an abbreviation for "car", not for "carriage" or any of the other words in the list that begins with "car"

    "" Input ""

    The input file contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.

    "" Output ""

    The output file contains the same number of lines as the input file. Each line of the output file contains the word from the corresponding line of the input file, followed by one blank space; and the shortest prefix that uniquely (without ambiguity) identifies this word.

    "" Sample input ""


    "" Output for sample input ""

    carbohydrate carboh
    cart cart
    carburetor carbu
    caramel cara
    caribou cari
    carbonic carboni
    cartilage carti
    carbon carbon
    carriage carr
    carton carto
    car car
    carbonate carbona

    © BrainMass Inc. brainmass.com December 24, 2021, 5:07 pm ad1c9bdddf

    Solution Preview


    Attached are a few documents related to the solution. The visio has the visual representation of the solution which can be used as reference while going through the write-up. I wasnot sure if you had visio or not, so have converted it into a html format as well.

    Solution as follows:

    1> Read the file either
    a> character by character till end of line (line feed or carriage return is reached) to create the word or
    b> read one word and go to the next line.
    c> read the complete line as it contains only 1 word.

    2> Create a Hash table or Hash Map, which stores the Name - Value pair combination. (As referred in Figure-1)
    a> The Name used in this Hash Table would be the Line Number
    b> The Value would be the value of the word read in Step 1.

    3> Create another Hash table or Hash Map, which will store the Name - Value pair of (As referred in Figure-2)
    a> the I/P word, which will be the Name and
    b> the Value will be an empty value or null.

    4> Create a sorted link list or a ...

    Solution Summary

    Shortest Prefixes are highlighted.