C-String Manipulation

The program operates in a series of rounds. In each round, it searches the collection to find the pair of fragments with the maximal overlap match and merges those two fragments. This match/merge operation decreases the total number of fragments by one. The program repeats the match/merge operation until only one fragment remains. Matching a pair of fragments means finding a position to align the two for the maximal overlapping match. In each round, you identify the pair of fragments in the collection with longest such overlap and merge them. Consider a collection with these fragments: s1: a l l i s w e l l s2: e l l t h a t e n s3: h a t e n d s4: t e n d s w e l l On the first round, the longest overlap found is a 6-character overlap between s2 and s3 when aligned as below: e l l t h a t e n h a t e n d The fragments s2 and s3 would be removed and replaced with their merged result s5: s5: e l l t h a t e n d The new, merged fragment (s5) is a candidate for future rounds, the two fragments it was composed from (s2 and s3) are no longer considered. On the next round, the longest overlap is 5 characters between s5 and s4 aligned as below: e l l t h a t e n d t e n d s w e l l The fragments s5 and s4 would be removed and replaced with their merged result s6: s6: e l l t h a t e n d s w e l l The last round merges s1 and s6 in their maximal overlap alignment of 3 characters: a l l i s w e l l e l l t h a t e n d s w e l l The one remaining fragment is the final result: a l l i s w e l l t h a t e n d s w e l l Note another kind of match possibility is when one fragment is contained within another Consider: s1: s w e l l t h a s2: e l l In this case, s2 is completely contained within s1. When these two fragments are merged, the result is simply s1. Your program can break ties arbitrarily. If there are several pairs with the same maximal overlap, choose whichever is easiest for you. If there are two equally maximal alignments for a pair (e.g. abxy and xyab merges to either abxyab or xyabxy), you can choose either. Similarly if two fragments have no overlap, their merge is simply the concatentation of the two strings in either order. Because of differences in how ties are broken, your final result might differ somewhat from our sample program. ## Deliverables This program should reads a file of text fragments and attempts to reconstruct the original document from the fragments. The fragments were created by duplicating the original document many times over and dividing each copy into pieces. The fragments overlap one another and your program will search for and align the overlapping string fragments to try to reassemble the fragments into their original order. Implementation details * ****Program operation**. The program takes one required argument, the filename containing the fragments. If no filename is given or the file cannot be opened, the program exits with an appropriate error message. Otherwise, it will reassemble the fragments using the greedy maximal match/merge and print the final merged result.** * ****Fragment file format**. The input files contain fragments in this format:** **#fragment 1##fragment 2#...#fragment N# ** **Each fragment is wrapped in a starting and ending # marker. A fragment can contain any character other than # (including spaces, newlines, etc.) This format is designed for reading fragment by fragment. Hint: consider using fscanf with a character exclusion set ( %[^#] ). And while I'm hinting, remember why you want to specify a limit whenever reading into a string.** * ****Data set size.** To simplify things, you can assume that the fragments in the data files are at most 1000 characters and a file will contain at most 10,000 fragments. These are large numbers and it is would be extravagant to preallocate storage to read in 10,000 x 1000 characters when most files will be much smaller. It is acceptable to declare an array of 10,000 char pointers and ***allocate storage for the strings as needed.***** * *******String-handling**. Fragments should be represented using C-strings. You may manipulate the string data using character array access, char * pointers, the standard string library functions (strncmp, strcat, sprintf, etc.), or a combination of strategies. By the time you're done, you should have a good understanding of how to handle C-strings!***** * *******Memory**. Your program should properly deallocate heap memory when no longer in use. Running your program under the valgrind tool can help you find memory leaks (memory that was allocated and abandoned) as well as give you information about misuse of memory. You can learn about valgrind from the links on the [CMSC 313 resource page][1]. The [quick start page][2] from the valgrind user's manual seems particularly helpful. Running your program under valgrind is as simple as:***** ***** valgrind --tool=memcheck --leak-check=full *program-to-execute args******