int min3(int x, int y, int z)
{
    if (x < y && x < z)
        return x;
    else
    if (y < z)
        return y;
    else
        return z;
}

int Wagner_Fischer(string& s, string& t, int d)
{
    int dist[s.length() + 1][2 * d + 1];
    int j = 0;
    bool flag;
    for (int i = 0; i <= s.length(); ++i)
    {
        flag = true;
        for (int k = max(0, i - d); k <= min((int)t.length(), i + d); ++k)
        {
            j = k - max(0, i - d);
            if (min(i, k) == 0)
            {
                dist[i][j] = max(i, k);
                if (dist[i][j] <= d)
                {
                    flag = false;
                }
                continue;
            }
            if (max(0, i - d) == 0)
            {
                if (s[i - 1] != t[k - 1])
                    dist[i][j] = min3(dist[i - 1][j] + 1, //удаление символа из s
                                      dist[i][j - 1] + 1, // вставка символа из t в s
                                      dist[i - 1][j - 1] + 1); //замена символа в s на символ из t (или наоборот)
                else
                    dist[i][j] = dist[i - 1][j - 1]; //просто переходим к префиксам на 1 меньше
            }
            else
            {
                if (s[i - 1] != t[k - 1])
                {
                    dist[i][j] = min(dist[i - 1][j] + 1, //удаление символа из s
                                     dist[i - 1][j + 1] + 1); // вставка символа из t в s
                    //замена символа в s на символ из t (или наоборот)
                    if (j > 0)
                    {
                        dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
                else
                    dist[i][j] = dist[i - 1][j]; //просто переходим к префиксам на 1 меньше
            }
            if (dist[i][j] <= d)
            {
                flag = false;
            }
        }
        //отсекаем заведомо неподходящие строки
        if (flag)
        {
            return 42;
        }
    }

    int last_id = min((int)t.length(), (int)s.length() + d) - max(0, (int)s.length() - d);
    return dist[s.length()][last_id];
}