Write a code for me with these specifications:

Objectives

$$ Give practice with recursion in C$.$

$$ Give practice with construction in C$.$

$$ Give additional practice with strings in C$.$

Story

You have repaired the break, and now the inscription is working as intended. You do now have some

free magic floating through the school. Knowing the exact amount of free magic is challenging,

and would take some time to measure.

While the free magic moves through the school random bad things happen, such as chocolate

disappearing or new homework assignments due at $11$:$59$pm given at noon that day. You could

use a spell to remove the magic, but without the exact knowledge on how much, you may cause

more problems by casting only part of a spell due to insufficient magic.

Your oracle has provided you some details of a particular spell which can clear out all the free

magic, but the effect of which is innocuous at worst. The details are sequences of glyphs that

occur consecutively in the incantation. Each sequence that the oracle has divined is of the same

length. It appears that no pauses exist in the incantation.

However, the oracle has not given you the order in which these sequences occur. You want to

determine what the proper full incantation. You will work on developing the incantation. For now

you will simply determine the smallest possible incantation that the spell could possibly be$.$

Problem

Given a set of sequences of characters each of which are the same length, determine the shortest

sequence of characters that contains all of them.

Input Specification

Input begins with a line containing $2$ integers, N and L $(1$ N $11$; $1$ L $100),$ representing

the number of sequences and the length of each incantation sequence.

The following line contains N space separated strings containing only upper and lower case

letters of length L$,$ each one representing the incantation segment given by the oracle.

$1$

Output Specification

Your program should print out the shortest incantation that contains ALL the given incantation

segments.

Example Input Output

Below is are example of cases that your program will be tested against. The below cases are not

meant to be extensive. It is your responsibility. You should work on developing your own cases.

Input Output

$34$ cdbabcd

abcd cdba babc

$45$ eebddbaabccbee

aabcc ccbee eebdd ddbaa

Example Explanation

Sample Case $1$

In the first case there are $3$ sequences of length $4$ given by the oracle. The oracle sequences are

abcd, cdba, and babc.

There are many ways an incantation could contain all the incantation sequences. The following

are possible incantations that contain all the sequences,

$$ abcdbabc

$$ abcdextracdbacharsbabc

$$ babcdba

The smallest possible incantation has $7$ characters. The one selected by the solution is cdbabcd.

Below help denotes the location of each oracle sequence in the resulting incantation by underlining

them,

$$ cdbabcd

$$ cdbabcd

$$ cdbabcd

Sample Case $2$

There are $4$ sequences, which will all be length $5.$ There are many possible incantations that

have the minimum length, which is $14$ in this case. The answer selected by the program is

eebddbaabccbee. The first $5$ characters is an oracle sequence. The next sequence begins at

the first $$d$.$ The next sequence begins at the first $$a$,$ and the last sequence begins at the first $$c$.$

$2$

Hints

$$ Read in your values first.

$$ Use an array of strings to hold onto the oracle sequences.

$$ Read in the strings using scanf with the string format specifier. It$$s easy.

$$ Use a loop to read them into the array.

$$ Don$$t try every possible string. Use the order of the sequences to help.

$$ Because oracle sequences must be contiguous in the result, and the sequences are all

the same length, different sequences must have different starting locations.

$$ Consider arranging the order of where each sequence will begin.

$$ Two different sequences that overlap will have some characters at the beginning and

some number of characters at the end come from different strings.

$$ When determining the optimal overlap, using the largest overlap possible

will ensure the shortest possible total incantation.

$$ Store the best sequence. Consider using global memory.

$$ Runtime is important for getting full credit problem.

$$ If you are using permutations and you wish to get full credit, you will need to compute

the best overlap between all oracle sequences at most once.

$$ These overlaps can be computed for each pair prior to running the permutation code.

$$ Computing values prior to another computation that needs them is commonly referred

to as precomputation.