C++ edit distance / string similarity function based on the Jaro-Winkler algorithm I wrote a short library function, based on an example from Rosetta, to compare two strings and determine similarity, using Jaro-Winkler.

A short copy-paste ready example:

main.cpp

#include &lt;string&gt;
#include &lt;iostream&gt;

#include "jaro_winkler.hpp"

int main() {
    std::string a { "DWAYNE" };
    std::string b { "DUANE" };

    std::cout &lt;&lt; "Similarity for '" &lt;&lt; a
              &lt;&lt; "' and '" &lt;&lt; b
              &lt;&lt; "': " &lt;&lt; edit_distance::jaro_winkler(a, b)
              &lt;&lt; std::endl;

    std::cout &lt;&lt; "Similarity for 'MARTHA' and 'MARHTA': "
              &lt;&lt; edit_distance::jaro_winkler("MARTHA", "MARHTA")
              &lt;&lt; std::endl;
    std::cout &lt;&lt; "Similarity for 'DIXON' and 'DICKSONX': "
              &lt;&lt; edit_distance::jaro_winkler("DIXON", "DICKSONX")
              &lt;&lt; std::endl;
    std::cout &lt;&lt; "Similarity for 'JELLYFISH' and 'SMELLYFISH': "
              &lt;&lt; edit_distance::jaro_winkler("JELLYFISH", "SMELLYFISH")
              &lt;&lt; std::endl;
}


jaro_winkler.hpp

#pragma once

#include &lt;cstddef&gt;
#include &lt;cstdint&gt;
#include &lt;algorithm&gt;
#include &lt;string_view&gt;

namespace edit_distance {
    template &lt;typename T = float&gt;
    inline T jaro(const std::string_view source,
                  const std::string_view target)
    {
        const unsigned sl = source.length();
        const unsigned tl = target.length();

        if (sl == 0 || tl == 0) return 0;

        const auto match_distance = (sl == 1 &amp;&amp; tl == 1)
                                        ? 0
                                        : (std::max(sl, tl) / 2 - 1);
        auto source_matches = new bool[sl] {0};
        auto target_matches = new bool[tl] {0};
        unsigned matches = 0;
        for (unsigned i = 0; i &lt; sl; ++i) {
            const auto end = std::min(i + match_distance + 1, tl);
            for (auto k = i &gt; match_distance ? (i - match_distance) : 0u; k &lt; end; ++k)
            {
                if (!target_matches[k] &amp;&amp; source[i] == target[k]) {
                    source_matches[i] = true;
                    target_matches[k] = true;
                    ++matches;
                    break;
                }
            }
        }
        if (matches == 0) {
            delete[] source_matches;
            delete[] target_matches;
            return 0;
        }

        T t = 0.0;
        unsigned k = 0;
        for (unsigned i = 0; i &lt; sl; ++i) {
            if (source_matches[i]) {
                while (!target_matches[k]) ++k;
                if (source[i] != target[k]) t += 0.5;
                ++k;
            }
        }

        const T m = matches;
        delete[] source_matches;
        delete[] target_matches;
        return (m / sl + m / tl + (m - t) / m) / 3.0;
    }

    template &lt;typename T = float&gt;
    inline T jaro_winkler(const std::string_view source,
                          const std::string_view target,
                          const unsigned prefix = 2,
                          const T boost_treshold = 0.7,
                          const T scaling_factor = 0.1)
    {
        const auto similarity = jaro&lt;T&gt;(source, target);

        if (similarity &gt; boost_treshold) {
            int common_prefix = 0;
            const int l = std::min((unsigned)std::min(source.length(), target.length()), prefix);
            for (; common_prefix &lt; l; ++common_prefix) {
                if (source[common_prefix] != target[common_prefix]) break;
            }
            return similarity + scaling_factor * common_prefix * (1 - similarity);
        } else {
            return similarity;
        }
    }
} // namespace edit_distance


I'd be happy to hear any comments or critiques.
Here are a few things that I immediately see in this code that have room for improvement:

template &lt;typename T = float&gt;


Assuming you only want floating point values passed as template parameters (Since you do floating point arithmetic later on), you could add:

static_assert(std::is_floating_point&lt;T&gt;::value, 
              "jaro can only be used with floating point types");




const unsigned sl = source.length();
const unsigned tl = target.length();


While the above may work for your code, the type for the length of the std::string_view isn't always guaranteed to be a plain unsigned int. Consider using std::size_t as the variable type, or std::string_view::size_type.



auto source_matches = new bool[sl] {0};
auto target_matches = new bool[tl] {0};



The use of auto is confusing here. It is hard to tell at first glance that you are meaning to use a dynamic array. auto doesn't shorten the type much either, so you may want to remove it.
Raw dynamic arrays are a large source of error. Consider using std::vector instead. This will also allow you to remove the deletes later on in your code.




for (unsigned i = 0; i &lt; sl; ++i)


You could use std::size_t here. Don't make assumptions about unsigned types.



delete[] source_matches;
delete[] target_matches;


Using a std::vector would allow you to remove this.



(unsigned)std::min(source.length(), target.length())


If you have to use a cast, prefer using static_cast, as it makes your intent clearer.