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.*; 
public class main { 


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 long sysNow() { 
  return System.nanoTime()/1000000; 
} 
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 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); 
  } 

}