SP2325 STRDIST - String Distance

Let A = a $ _{1} $ a $ _{2} $ ...a $ _{k} $ and B = b $ _{1} $ b $ _{2} $ ...b $ _{l} $ be strings of lengths k and l, respectively. The string distance between A and B is defined in the following way (d\[i,j\] is the distance of substrings a $ _{1} $ ...a $ _{i} $ and b $ _{1} $ ...b $ _{j} $ , where 0 ≤ i ≤ k and 0 ≤ j ≤ l -- i or j being 0 represents the empty substring). The definition for d\[i, j\] is d\[0, 0\] = 0 and for (i, j) ≠ (0, 0) d\[i, j\] is the minimum of all that apply: - d\[i, j - 1\] + 1, if j > 0 - d\[i - 1, j\] + 1, if i > 0 - d\[i - 1, j - 1\], if i > 0, j > 0, and a $ _{i} $ = b $ _{j} $ - d\[i - 1, j - 1\] + 1, if i > 0, j > 0, and a $ _{i} $ ≠ b $ _{j} $ - d\[i - 2, j - 2\] + 1, if i ≥ 2, j ≥ 2, a $ _{i} $ = b $ _{j-1} $ , and a $ _{i-1} $ = b $ _{j} $ The distance between A and B is equal to d\[k,l\]. For two given strings A and B, compute their distance knowing that it is not higher than 100.

In the first line, k and l are given, giving the lengths of the strings A and B (1 ≤ k, l ≤ 10 $ ^{5} $ ). In the second and third lines strings A and B, respectively, are given. A and B contain only lowercase letters of the English alphabet.

In the first line, write one number, the distance between A and B, followed by a newline.