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 - USE LONG to fix JVM SAFE POINTS. for (long _j = 1; _j <= m; _j++) { int j = (int) _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); } static List repeat(A a, int n) { List l = new ArrayList(); for (int i = 0; i < n; i++) l.add(a); return l; } }