Count Substrings with Bounded Edit Distance

Given two strings \(A\) and \(B\) and an integer \(K\), count the number of non-empty substrings of \(B\) whose edit distance to \(A\) is at most \(K\). The edit distance between two strings is defined as the minimum number of operations (insertion, deletion, or substitution) required to transform one string into the other.

A substring refers to any contiguous segment of \(B\) (substrings at different positions are counted separately even if they are identical). The standard dynamic programming formulation for computing the edit distance is as follows:

$$ \text{dp}[i][j] = \begin{cases} j, & \text{if } i = 0, \\ i, & \text{if } j = 0, \\ \min\begin{cases} \text{dp}[i-1][j] + 1, \\ \text{dp}[i][j-1] + 1, \\ \text{dp}[i-1][j-1] + \begin{cases}0 & \text{if } A_{i} = B_{j} \ 1 & \text{otherwise}\end{cases} \end{cases}, & \text{otherwise.} \end{cases} $$

Your task is to compute the number of substrings \(S\) of \(B\) such that \(\text{EditDistance}(A, S) \le K\).

inputFormat

The input consists of three lines:

1. The first line contains an integer \(K\) (\(0 \le K \le 100\)).
2. The second line contains the string \(A\).
3. The third line contains the string \(B\).

outputFormat

Output a single integer representing the number of non-empty substrings of \(B\) whose edit distance to \(A\) is at most \(K\).

sample

1
abc
abc

3