1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
// Copyright 2023 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_
#define BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_
#include <stddef.h>
#include <optional>
#include <string_view>
#include "base/base_export.h"
namespace base {
// Returns the Levenshtein distance of `a` and `b`. Edits, inserts and removes
// each count as one step.
// If `k = max_distance` is provided, the distance is only correctly calculated
// up to k. In case the actual Levenshtein distance is larger than k, k+1 is
// returned instead. This is useful for checking whether the distance is at most
// some small constant, since the algorithm is more efficient in this case.
// Complexity:
// - Without k: O(|a| * |b|) time and O(max(|a|, |b|)) memory.
// - With k: O(min(|a|, |b|) * k + k) time and O(k) memory.
BASE_EXPORT size_t
LevenshteinDistance(std::string_view a,
std::string_view b,
std::optional<size_t> max_distance = std::nullopt);
BASE_EXPORT size_t
LevenshteinDistance(std::u16string_view a,
std::u16string_view b,
std::optional<size_t> max_distance = std::nullopt);
} // namespace base
#endif // BASE_STRINGS_LEVENSHTEIN_DISTANCE_H_
|
