Description

Given two strings $A$ and $B$. How many non-empty substrings of $B$ have an edit distance to $A$ that is at most $K$?

A “substring” means a consecutive segment of $B$. Substrings with the same content but different positions are counted multiple times. The “edit distance” between two strings is the minimum number of operations needed to change one string into the other. Each operation can insert, delete, or replace one character.

Input Format

The first line contains a non-negative integer $K$. The next two lines each contain a string of uppercase letters, representing $A$ and $B$ respectively.

Output Format

Output one line containing an integer, which is the required answer.

1
AAA
AABBAAB

5

Hint

For $100\%$ of the data, $K\leq5$, both strings are non-empty, and the sum of their lengths is less than $10^5$.

Translated by ChatGPT 5