You are investigating the possible common ancestors of different species. One of the techniques you use is to search for common substrings of DNA between species. The longer the common substring, the more closely the species are related. In this case you will be looking for substrings of DNA which appear in the DNA of each of two different species. Each DNA sample is represented by a sequence of any of the letters "ACGT" in any order.
Given two strings representing DNA from two species find the length of the longest string which is a substring of both of the input strings.
In this problem "substring" has the usual definition. A string X is a substring of a string Y if and only if string X can be created from string Y by deleting zero or more consecutive characters from the start of string Y, and deleting zero or more consecutive characters from the end of string Y.
For example
"AAAAAAAAAAAAAAAAAAAAACCCGGGGGGGGGGGGG"
"AAAACCCGGGGGGGGGGGGGGGGTTTTTTTTTGGGGGGGGGGGG"
returns 20 corresponding to "AAAACCCGGGGGGGGGGGGG" |