With vehicle tracking data becoming an important sensor data resource for a range of applications related to traffic assessment and prediction, fast and accurate mapmatching algorithms become a necessary means to ultimately utilize this data. This work proposes a fast mapmatching algorithm which exploits tracking data error estimates in a provably correct way and offers a quality guarantee for the computed result trajectory. A new model for the map-matching task is introduced which takes tracking error estimates into account. The proposed Adaptive Clipping algorithm (i) provably solves this map-matching task and (ii) utilizes the weak Fr?echet distance to measure similarity between curves. The algorithm uses the error estimates in the trajectory data to reduce the search space (error-aware pruning), while offering the quality guarantee of finding a curve which minimizes the weak Fr?echet distance to the vehicle trajectory among all possible curves in the road network. Moreover, this work introduces an outputsensitive variant of an existing weak Fr?echet map-matching algorithm, which is also employed in the Adaptive Clipping algorithm. Output-sensitiveness paired with error-aware pruning makes Adaptive Clipping the first map-matching algorithm that provably solves a well-defined map-matching task. An experimental evaluation establishes further that Adaptive Clipping is also in a practical setting a fast algorithm that at the same time produces high-quality matching results.