Description
In this lab, you will implement a program to find the longest match between two
strings (maximum overlap between two strings).
Problem Description
Finding the maximum overlap between two strings has many applications in
security, DNA sequencing, …
To see how it works, consider the following 6 sentences, we start by finding the
maximum overlap between any 2 strings
eers are paid t (1)
aid to mak (2)
e things work (3)
to make things (4)
Engineers are p (5)
The maximum overlap is between (1) and (5) and of length 10
eers are paid t (1)
Engineers are p (5)
Combined to produce (6). Now we remove (1) and (5) and replace them with (6)
Engineers are paid t (6)
aid to mak (2)
e things work (3)
to make things (4)
Then the maximum overlap is between (3) and (4), and of length 8.
e things work (3)
to make things (4)
we combine them to produce (7).
Now we remove (3) and (4) and replace them by (7).
to make things work (7)
Engineers are paid t (6)
aid to mak (2)
The max overlap is between (7) and (2) and of length 6
to make things work (7)
aid to mak (2)
We combine them to produce (8)
aid to make things work (8)
Engineers are paid t (6)
The only overlap is between (8) and (6), and of length 5. Combining them to
produce
Engineers are paid to make things work
Note that we are considering the overlap at the boundary of the string
only. That is a match from the beginning of the first string to the end of
either the first or the second string.
Problem Statement
Write a C program to read 2 strings from the standard input. The two strings are
terminated by a new line (use fgets).
Find the length of the maximum overlap and combine these two strings are
shown above.
To make it easy on you, submit two programs
L5A.c that displays on the standard output a single integer that is the maximum
overlap between these 2 strings followed by a new line.
L5B.c similar to the above program, but adds on a separate line the combination
of these two strings as shown above followed by a new line.
