Question

A substring of some character string is a contiguous sequence of characters in that string (which is different than a subsequence, of course). Suppose you are given two character strings, X and Y , with respective lengths n and m. Describe an efficient algorithm for finding a longest common substring of X and Y .For each algorithm:i. Explain the main idea and approach.Write appropriate pseudo-code.Trace it on at least three different examples, including at least a canonical case and two corner cases.

iv. Give a proof of correctness.v. Give a worst-case asymptotic running time analysis.

Answer 1

create a 2-dimensional array, let both rows represent the strings X and Y.

check for the common characters within a string and compare them with the other string value.

If there is a match, append it to the array rows.

After iterating over both strings for the substring, get the longest common substring for both strings and print.

Step-by-step explanation:

The algorithm should create an array that holds the substrings, then use the max function to get the largest or longest substring in the array.