fuzzy substring

fuzzy_string_distance.cpp

// ==========================================================
template <typename T>
typename T::value_type levenshtein_distance(const T& src, const T& dst) {
  const typename T::size_type m = src.size();
  const typename T::size_type n = dst.size();
  
  if (m == 0) {
    return n;
  }
  
  if (n == 0) {
    return m;
  }

  std::vector<std::vector<typename T::value_type>> matrix(m + 1);

  for (typename T::size_type i = 0; i <= m; ++i) {
    matrix[i].resize(n + 1);
    matrix[i][0] = i;
  }
  
  for (typename T::size_type i = 0; i <= n; ++i) {
    matrix[0][i] = 0;
  }

  typename T::value_type above_cell, left_cell, diagonal_cell, cost, min;

  for (typename T::size_type i = 1; i <= m; ++i) {
    min = std::numeric_limits<typename T::value_type>::max();
    for(typename T::size_type j = 1; j <= n ; ++j) {
      cost = src[i - 1] == dst[j - 1] ? 0 : 1;
      above_cell = matrix[i - 1][j];
      left_cell = matrix[i][j - 1];
      diagonal_cell = matrix[i - 1][j - 1];
      matrix[i][j] = std::min(std::min(above_cell + 1, left_cell + 1), diagonal_cell + cost);
      min = std::min(min, matrix[i][j]);
    }
  }
   
   /*
   for (typename T::size_type i = 0; i < matrix.size(); ++i) { 
    for(typename T::size_type j = 0; j < matrix[i].size() ; ++j) {
	  printf("%d", matrix[i][j]);
    }
	printf("\n");
  }
  */
	
  return min;
}