DNA Subsequences#3527

DNA Subsequences

2 seconds

256 megabytes

Very easy

Thomas, a computer scientist who works with DNA sequences, needs to compute the longest common subsequences of given pairs of strings.

Consider an alphabet $Σ$ of letters and a word $w = a_{1} a_{2} \dots a_{r}$ w = a_1 a_2 \ldots a_r, where $a_{i} \in Σ$ a_i \in \Sigma for $i = 1, 2, \dots, r$ i = 1, 2, \ldots, r. A subsequence of $w$ is a word $x = a_{i_{1}} a_{i_{2}} \dots a_{i_{s}}$ x = a_{i_1} a_{i_2} \ldots a_{i_s} such that $1 \leq i_{1} < i_{2} < \dots < i_{s} \leq r$ 1 \leq i_1 < i_2 < \ldots < i_s \leq r. Subsequence $x$ is a segment of $w$ if $i_{j + 1} = i_{j} + 1$ i_{j+1} = i_j + 1 for $j = 1, 2, \dots, s - 1$ j = 1, 2, \ldots, s-1. For example, the word lovely 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}$ w_1 and $w_{2}$ w_2 if it is a subsequence of both words. A longest common subsequence of $w_{1}$ w_1 and $w_{2}$ w_2 is a common subsequence of $w_{1}$ w_1 and $w_{2}$ w_2 having the largest possible length. For example, consider the words $w_{1} = lovxxelyxxxxx$ w_1 = \texttt{lovxxelyxxxxx} and $w_{2} = xxxxxxxlovely$ w_2 = \texttt{xxxxxxxlovely}. The words $w_{3} = lovely$ w_3 = \texttt{lovely} and $w_{4} = xxxxxxx$ w_4 = \texttt{xxxxxxx}, the latter of length $7$ , are both common subsequences of $w_{1}$ w_1 and $w_{2}$ w_2. In fact, $w_{4}$ w_4 is their longest common subsequence. Notice that the empty string, of length zero, is always a common subsequence, although not necessarily the longest.

In Thomas's case, there is an extra requirement: the common subsequence must be formed from common segments of length $K$ or more. For example, if $K = 3$ K = 3, then $w_{3} = lovely$ w_3 = \texttt{lovely} is an acceptable common subsequence of $w_{1}$ w_1 and $w_{2}$ w_2, whereas $w_{4} = xxxxxxx$ w_4 = \texttt{xxxxxxx}, though of length $7$ and 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$ ( $1 \leq K \leq 100$ 1 \leq K \leq 100), the minimum length of common segments. The next two lines each contain a string of lowercase letters from the $26$ -letter English alphabet. The length $l$ of each string satisfies $1 \leq l \leq 1 0^{3}$ 1 \leq l \leq 10^3. There are no spaces on any line in the input. The end of the input is indicated by a line containing a single zero.

Output

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

Examples

Example 1