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=a1a2ar, where ai ∈ Σ, for i = 1, 2, …,r. A subsequence of w is a word x=ai1ai2ais such that 1 ≤ i1 < i2 < … < isr. Subsequence x is a segment of w if ij+1=ij + 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 w1 and w2 if it is a subsequence of each of the two words. A longest common subsequence of w1 and w2 is a common subsequence of w1 and w2 having the largest possible length. For example, consider the words w1=lovxxelyxxxxx and w2=xxxxxxxlovely. The words w3=lovely and w4=xxxxxxx, the latter of length 7, are both common subsequences of w1 and w2. In fact, w4 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 ≤ 100. The next two lines contain each a string on lowercase letters from the regular alphabet of 26 letters. The length l of each string satisfies the inequality 1 ≤ l ≤ 103. There are no spaces on any line in the input. The end of the input is indicated by a line containing a zero.



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.




hide comments
amiri: 2016-09-15 22:38:35

Best problem for test your debugging skill in dp matrices :D

Last edit: 2017-01-14 01:50:48
razor123: 2016-08-25 07:51:37

Weak test cases!! O(l^3) got accepted.

SUBHAJIT GORAI: 2016-08-07 09:45:27

those who didn't got the question ..consider a subsequence which is in result ...the subsequence must be broken down into segments of length greater than k in both the strings .. and then we have to maximize the length of the subsequence ..

begin_88: 2016-06-07 15:24:00

Nice Question...

Last edit: 2016-06-07 15:25:10
code_maxx: 2015-10-06 13:51:08

O(l^3) algo passes with the test cases given, while a better algorithm can do the trick in O(l*l*K). Could the testcases be changed ?

Augusto: 2015-09-18 19:41:53

Got accepted even when cases like
took several seconds in my computer

here's a tricky case:

and one somebody else commented:

(Tjandra Satria Gunawan)(曾毅昆): 2015-08-09 08:40:34

wow, test case are weird, O(2*(n^3)) is faster than O(3*(n^2)) :o

(Tjandra Satria Gunawan)(曾毅昆): 2015-08-09 08:24:41

got AC with optimized O(l^3) algo :p

Walid Amin: 2015-07-10 00:05:56

@ priteshranjan
No, the subsequence must be formed from common segments having length K or more.
and k here is 5
Proof that answer can't be 8:
we have the k=5 so we can't get LCS formed from segment of length <5 and the length of the second string is 8 so the only way we can form LCS of length 8 is to be formed from only one segment because if it is formed a segment of minimum length (5) the other will be 3 and can't be considered
and there is no segment of length 8 that match
optimal solution is 7 "abcdefg" it can be found as one segment

Amogh: 2015-06-20 14:07:09

my 100th :)

Added by:Diego Satoba
Time limit:0.779s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CPP C++ 4.3.2 JAVA PAS-GPC PAS-FPC
Resource:South American Regional Contests 2008