// Calculates the fuzzy match of needle in haystack,
// using a modified version of the Levenshtein distance algorithm.
// ported from: http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/

static Pair<Int> levenSubstringIC_withIndex(S haystack, S needle) {
  int m = strL(needle), n = strL(haystack);

  // base cases
  if (m == 1) {
    int idx = indexOfIC(haystack, needle);
    ret idx < 0 ? pair(0, 1) : pair(idx, 0);
  }
  if (m == 0)
    ret pair(0, m);

  int[] row1 = new int[n+1], row2 = new int[n+1];
  for i to m: {
    row2[0] = i+1;
    for j to n: {
      int cost = neqic(needle.charAt(i), haystack.charAt(j)) ? 1 : 0;
      row2[j+1] = min3(row1[j+1]+1,   // deletion
                       row2[j]+1,     // insertion
                       row1[j]+cost); // substitution
    }
    int[] temp = row1;
    row1 = row2;
    row2 = temp;
  }
  Pair<Int> p = minOfIntArray_withIndex(row1);
  ret pair(max(0, p.a-m), p.b);
}