* @brief Levenshtein distance between two strings, capped for speed. */
| 37 | * @brief Levenshtein distance between two strings, capped for speed. |
| 38 | */ |
| 39 | static int editDistance(const QString& a, const QString& b) |
| 40 | { |
| 41 | const int la = a.size(); |
| 42 | const int lb = b.size(); |
| 43 | if (la == 0) |
| 44 | return lb; |
| 45 | |
| 46 | if (lb == 0) |
| 47 | return la; |
| 48 | |
| 49 | QVector<int> prev(lb + 1); |
| 50 | QVector<int> curr(lb + 1); |
| 51 | for (int j = 0; j <= lb; ++j) |
| 52 | prev[j] = j; |
| 53 | |
| 54 | for (int i = 1; i <= la; ++i) { |
| 55 | curr[0] = i; |
| 56 | for (int j = 1; j <= lb; ++j) { |
| 57 | const int cost = (a.at(i - 1).toLower() == b.at(j - 1).toLower()) ? 0 : 1; |
| 58 | curr[j] = std::min({curr[j - 1] + 1, prev[j] + 1, prev[j - 1] + cost}); |
| 59 | } |
| 60 | std::swap(prev, curr); |
| 61 | } |
| 62 | return prev[lb]; |
| 63 | } |
| 64 | |
| 65 | /** |
| 66 | * @brief Lower-is-better score: prefers names sharing the dotted prefix. |