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?
Input
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 ≤ 10^{3}. There are no spaces on any line in the input. The end of the input is indicated by a line containing a zero.
Output
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.
Example
Input: 3 lovxxelyxxxxx xxxxxxxlovely 1 lovxxelyxxxxx xxxxxxxlovely 3 lovxxxelxyxxxx xxxlovelyxxxxxxx 4 lovxxxelyxxx xxxxxxlovely 0 Output: 6 7 10 0
hide comments
amiri:
20160915 22:38:35
Best problem for test your debugging skill in dp matrices :D Last edit: 20170114 01:50:48 

razor123:
20160825 07:51:37
Weak test cases!! O(l^3) got accepted. 

SUBHAJIT GORAI:
20160807 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:
20160607 15:24:00
Nice Question... Last edit: 20160607 15:25:10 

code_maxx:
20151006 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:
20150918 19:41:53
Got accepted even when cases like


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150809 08:40:34
wow, test case are weird, O(2*(n^3)) is faster than O(3*(n^2)) :o 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150809 08:24:41
got AC with optimized O(l^3) algo :p 

Walid Amin:
20150710 00:05:56
@ priteshranjan


Amogh:
20150620 14:07:09
my 100th :) 
Added by:  Diego Satoba 
Date:  20081123 
Time limit:  0.779s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CPP C++ 4.3.2 JAVA PASGPC PASFPC 
Resource:  South American Regional Contests 2008 