Implement function to calculate Damerau-Levenshtein distance between two strings.

PiperOrigin-RevId: 481568970
Change-Id: Icb132348f62fed4c0168aac4963b3313a060890b

1 files changed, 35 insertions, 0 deletions

diff --git a/absl/strings/internal/damerau_levenshtein_distance.h b/absl/strings/internal/damerau_levenshtein_distance.h
new file mode 100644
index 00000000..b9bb6fe1
--- /dev/null
+++ b/absl/strings/internal/damerau_levenshtein_distance.h
@@ -0,0 +1,35 @@
+// Copyright 2022 The Abseil Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_STRINGS_INTERNAL_DAMERAU_LEVENSHTEIN_DISTANCE_H_
+#define ABSL_STRINGS_INTERNAL_DAMERAU_LEVENSHTEIN_DISTANCE_H_
+
+#include <numeric>
+#include <vector>
+
+#include "absl/strings/string_view.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace strings_internal {
+// Calculate DamerauLevenshtein distance between two strings.
+// When the distance is larger than cutoff, the code just returns cutoff + 1.
+size_t CappedDamerauLevenshteinDistance(absl::string_view s1,
+                                        absl::string_view s2, uint8_t cutoff);
+
+}  // namespace strings_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
+
+#endif  // ABSL_STRINGS_INTERNAL_DAMERAU_LEVENSHTEIN_DISTANCE_H_