A subsequence of a string s is an ordered sequence of characters, not necessarily consecutive, from s. E.g. ‘AGCA’ is a subsequence of ‘ATTGCTA’.

A common subsequence of two strings s1 and s2 is a subsequence that appears both in s1 and s2. E.g. ‘TTA’ is a common subsequence of ‘ATCTGAT’ and ‘TGCATA’.

We want to find a longest common subsequence (or LCS) of two strings s1 and s2. E.g. ‘TCTA’ and ‘TGAT’ are longest common subsequences of ‘ATCTGAT’ and ‘TGCATA’.

Assignment

Write a Python function findLCS which takes two strings as parameter and which return a longest common subsequence of these strings. The function should implement an dynamic programming approach.

Example

>>> findLCS('ATTTCCTATCCATTTACCACC', 'TTCCATTATCGGTATTAATTACAA')
'TTCCTATCATTTACA'