2.4 Longest Common Subsequence

You must submit this in an archive named "lcs.zip".

Flavor text: Dr. Albert Wily and Dr. Thomas Light are embroiled in a copyright lawsuit over the alledged duplication of software in the operating system of Bass from Proto Man (and thus Mega Man). Dr. Light used Beat to steal the source code which you must now analyze to determine the largest copied segment.

You must implement a dynamic programming solution to the Longest Common Subsequence problem.

Your program should accept two ASCII strings (perhaps specified as paths to files.)

Your program must output the longest common subsequence.

You must test your program on strings of at least 5000 characters.

Your program must output the time it took to solve the problem (not read in the input and solve the problem.)

If you want to, follow these directions instead.

Warning: Many people errorneously implement the longest common substring. The longest common substring of Artist and Artsy is Art. The longest common subsequence of Artist and Artsy is Arts. You are implementing longest common subsequence.