Reference no: EM1380221
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 ""
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
"" 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
|
Solving single source shortest paths problem
: Here is a proposed algorithm to solve single source shortest paths problem in a weighted directed graph G with possibly negative edges weights.
|
|
Modify bellman ford algorithm to find negative weight cycle
: Demonstrate how to modify the Bellman Ford algorithm to find and print a negative weight cycle in a weighted directed graph G if one exists.
|
|
Differentiate between the interaction types and styles
: Explain the conceptual model employed in the design of these types. Describe the analogies and concepts these monitors expose to users, including the task-domain objects users manipulate on the screen.
|
|
Find the checksum field in a single parity bit scheme
: Assume that the information content of a packet is the bit pattern 1111000010100101 and an even parity is being used
|
|
Question about shortest prefixes
: 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.
|
|
Wage calculator with tax calculations
: Wage Calculator with Tax Calculations - Develop an application that calculates an employee's earnings
|
|
Create a program that reads product number and prices
: The Rinky Dooflingy Corporation produces different kinds of doofingies, each identified b a product number. Create a program that reads product number and rates and stores these values in two arrays,
|
|
Question about arrays, vector and stl
: Suppose if x denotes the mean of a sequence of numbers x1, x2,.....xn, variance is the average of the squares of the deviations of numbers from the mean.
|
|
Computing the total dollar sales
: A corporation has a product line that includes five items that sell for $100, $75, $120, $150, and $35. There are four salespersons working for this corporation,
|