Lev K
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <limits.h>
 
using namespace std;
 
// Datatypes
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
typedef long long ll;
typedef long double ld;
 
// Define
#define sz(a)             int((a).size()) 
#define pb                push_back 
#define all(c)            (c).begin(),(c).end() 
#define present(c,x)      ((c).find(x) != (c).end()) 
#define cpresent(c,x)     (find(all(c),x) != (c).end()) 
#define FOR(_i,_n)        for(int (_i) = 0; (_i) < (_n); (_i)++)
#define MP make_pair
 
// Constants
const double eps = 1e-8; 
const double PI = 3.1415926535897932384626433832795;
 
#define INPUT_FILE "distance.in"
#define OUTPUT_FILE "distance.out"
 
string s1;
string s2;
vi r; 
 
// Time O(K*L)
// Memory O(K)
 
int main(void)
{
#ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    freopen(INPUT_FILE, "r", stdin);
    freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    s1.resize(100010);
    s2.resize(100010);
 
    getline(cin, s1); 
    getline(cin, s2);
 
    int kk;
    cin >> kk;
 
    if(s2.size() > s1.size())
        swap(s1, s2);
 
    int N = s1.size(), K = s2.size();
 
    int mod = 2*kk+1;
 
    r.resize(mod);
 
    for(int i = 0; i < mod; i++)
        r[i] = i;
 
    int j = 1;
    for(int i = 1; i <= N; i++)
    {
        int l = max(j-kk, 1);
        int h = min(j+kk, K);
        if(l == 1)
            r[0] = i;
        int p = i - 1; 
        for(int jj = l; jj <= h; jj++)
        {
            int t = r[jj%mod];
            r[jj%mod] =  min(min(t + 1, r[(jj-1)%mod] + 1), p + ((s1[i-1] == s2[jj-1])?0:1));
            p = t;
        }
        j++;
    }
 
    if(r[K%mod] > kk)
        cout << "Infinity" << endl;
    else
        cout << r[K%mod] << endl;
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.