SP3408 SAMER08D - DNA Sequences

Thomas, a computer scientist that works with DNA sequences, needs to compute longest common subsequences of given pairs of strings. Consider an alphabet Σ of letters and a word _w_=_a_ $ _{1} $ _a_ $ _{2} $ …_a_ $ _{r} $ , where _a_ $ _{i} $ ∈ Σ, for _i_ = 1, 2, …,_r_. A _subsequence_ of _w_ is a word _x_=_a_ $ _{i1} $ _a_ $ _{i2} $ …_a_ $ _{is} $ such that 1 i $ _{1} $ < _i_ $ _{2} $ < … < _i_ $ _{s} $ r. Subsequence _x_ is a _segment_ of _w_ if _i_ $ _{j+1} $ =_i_ $ _{j} $ + 1, for _j_ = 1,2, …,_s_ -1. For example the word ove is a segment of the word lovely, whereas the word loly is a subsequence of lovely, but not a segment. A word is a _common subsequence_ of two words _w_ $ _{1} $ and _w_ $ _{2} $ if it is a subsequence of each of the two words. A _longest common subsequence_ of _w_ $ _{1} $ and _w_ $ _{2} $ is a common subsequence of _w_ $ _{1} $ and _w_ $ _{2} $ having the largest possible length. For example, consider the words _w_ $ _{1} $ =lovxxelyxxxxx and _w_ $ _{2} $ =xxxxxxxlovely. The words _w_ $ _{3} $ =lovely and _w_ $ _{4} $ =xxxxxxx, the latter of length 7, are both common subsequences of _w_ $ _{1} $ and _w_ $ _{2} $ . In fact, _w_ $ _{4} $ is their longest common subsequence. Notice that the empty word, of length zero, is always a common subsequence, although not necessarily the longest. In the case of Thomas, there is an extra requirement: the subsequence must be formed from common segments having length _K_ or more. For example, if Thomas decides that _K_=3, then he considers lovely to be an acceptable common subsequence of lovxxelyxxxxx and xxxxxxxlovely, whereas xxxxxxx, which has length 7 and is also a common subsequence, is not acceptable. Can you help Thomas?

The input contains several test cases. The first line of a test case contains an integer _K_ representing the minimum length of common segments, where 1 K l of each string satisfies the inequality 1 l

For each test case in the input, your program must print a single line, containing the length of the longest subsequence formed by consecutive segments of length at least _K_ from both strings. If no such common subsequence of length greater than zero exists, then 0 must be printed.