import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;


class main {


static int leven_limited(String left, String right, int threshold) {
  if (--threshold < 0) return 0;

  int n = left.length(); // length of left
  int m = right.length(); // length of right

  // if one string is empty, the edit distance is necessarily the length
  // of the other
  if (n == 0) {
      return m <= threshold ? m : threshold+1;
  } else if (m == 0) {
      return n <= threshold ? n : threshold+1;
  }

  if (n > m) {
      // swap the two strings to consume less memory
      final String tmp = left;
      left = right;
      right = tmp;
      n = m;
      m = right.length();
  }

  int[] p = new int[n + 1]; // 'previous' cost array, horizontally
  int[] d = new int[n + 1]; // cost array, horizontally
  int[] tempD; // placeholder to assist in swapping p and d

  // fill in starting table values
  final int boundary = Math.min(n, threshold) + 1;
  for (int i = 0; i < boundary; i++) {
      p[i] = i;
  }
  // these fills ensure that the value above the rightmost entry of our
  // stripe will be ignored in following loop iterations
  Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
  Arrays.fill(d, Integer.MAX_VALUE);

  // iterates through t
  for (int j = 1; j <= m; j++) {
      final char rightJ = right.charAt(j - 1); // jth character of right
      d[0] = j;

      // compute stripe indices, constrain to array size
      final int min = Math.max(1, j - threshold);
      final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(
              n, j + threshold);

      // the stripe may lead off of the table if s and t are of different
      // sizes
      if (min > max) {
          return threshold+1;
      }

      // ignore entry left of leftmost
      if (min > 1) {
          d[min - 1] = Integer.MAX_VALUE;
      }

      // iterates through [min, max] in s
      for (int i = min; i <= max; i++) {
          if (left.charAt(i - 1) == rightJ) {
              // diagonally left and up
              d[i] = p[i - 1];
          } else {
              // 1 + minimum of cell to the left, to the top, diagonally
              // left and up
              d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
          }
      }

      // copy current distance counts to 'previous row' distance counts
      tempD = p;
      p = d;
      d = tempD;
  }

  // if p[n] is greater than the threshold, there's no guarantee on it
  // being the correct
  // distance
  if (p[n] <= threshold) {
      return p[n];
  }
  return threshold+1;
}
static int n = 1000000;
static String a = repeat('a', n) + repeat('b', n);
static String b = repeat('a', n+10) + repeat('b', n-10);

public static void main(final String[] args) throws Exception {
  for (int max = 0; max <= 20; max++)
    test(max);
  test(100);
  test(1000);
  test(10000);
  test(100000);
  test(1000000);
  test(10000000);
  test(100000000);
}

static void test(int max) {
  long startTime = sysNow();
  System.out.println("max " + max + " => " + leven_limited(a, b, max));
  System.out.println((sysNow()-startTime) + " ms");
}
static String repeat(char c, int n) {
  n = Math.max(n, 0);
  char[] chars = new char[n];
  for (int i = 0; i < n; i++)
    chars[i] = c;
  return new String(chars);
}

static <A> List<A> repeat(A a, int n) {
  n = Math.max(n, 0);
  List<A> l = new ArrayList(n);
  for (int i = 0; i < n; i++)
    l.add(a);
  return l;
}

static <A> List<A> repeat(int n, A a) {
  return repeat(a, n);
}
static long sysNow() {
  return System.nanoTime()/1000000;
}

}