1 | // Copyright (C) 2021 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only WITH Qt-GPL-exception-1.0 |
3 | |
4 | #include "editdistance.h" |
5 | |
6 | QT_BEGIN_NAMESPACE |
7 | |
8 | int editDistance(const QString &s, const QString &t) |
9 | { |
10 | #define D(i, j) d[(i)*n + (j)] |
11 | int i; |
12 | int j; |
13 | qsizetype m = s.size() + 1; |
14 | qsizetype n = t.size() + 1; |
15 | int *d = new int[m * n]; |
16 | int result; |
17 | |
18 | for (i = 0; i < m; ++i) |
19 | D(i, 0) = i; |
20 | for (j = 0; j < n; ++j) |
21 | D(0, j) = j; |
22 | for (i = 1; i < m; ++i) { |
23 | for (j = 1; j < n; ++j) { |
24 | if (s[i - 1] == t[j - 1]) { |
25 | D(i, j) = D(i - 1, j - 1); |
26 | } else { |
27 | int x = D(i - 1, j); |
28 | int y = D(i - 1, j - 1); |
29 | int z = D(i, j - 1); |
30 | D(i, j) = 1 + qMin(a: qMin(a: x, b: y), b: z); |
31 | } |
32 | } |
33 | } |
34 | result = D(m - 1, n - 1); |
35 | delete[] d; |
36 | return result; |
37 | #undef D |
38 | } |
39 | |
40 | QString nearestName(const QString &actual, const QSet<QString> &candidates) |
41 | { |
42 | if (actual.isEmpty()) |
43 | return QString(); |
44 | |
45 | int deltaBest = 10000; |
46 | int numBest = 0; |
47 | QString best; |
48 | |
49 | for (const auto &candidate : candidates) { |
50 | if (candidate[0] == actual[0]) { |
51 | int delta = editDistance(s: actual, t: candidate); |
52 | if (delta < deltaBest) { |
53 | deltaBest = delta; |
54 | numBest = 1; |
55 | best = candidate; |
56 | } else if (delta == deltaBest) { |
57 | ++numBest; |
58 | } |
59 | } |
60 | } |
61 | |
62 | if (numBest == 1 && deltaBest <= 2 && actual.size() + best.size() >= 5) |
63 | return best; |
64 | |
65 | return QString(); |
66 | } |
67 | |
68 | QT_END_NAMESPACE |
69 | |