Find similarity between two strings in C++

This post will discuss how to find similarities between two strings in C++.

There are numerous algorithms to check similarity between two strings like Edit distance and Jaro-Winkler similarity. Edit distance checks how dissimilar two strings are to each other by counting the minimum number of operations required to transform one string to another. Jaro–Winkler similarity uses a prefix scale which gives more favorable ratings to strings that match from the beginning for a set prefix length.

The following solution uses Edit distance to calculate the similarity between two strings between 0 and 1. It can be easily modified to calculate string similarity in percentage and ignore case if needed.

#include <iostream>

#include <algorithm>

#include <string>

int getEditDistance(std::string first, std::string second)

{

int m = first.length();

int n = second.length();

int T[m + 1][n + 1];

for (int i = 1; i <= m; i++) {

T[i][0] = i;

}

for (int j = 1; j <= n; j++) {

T[0][j] = j;

}

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

int weight = first[i - 1] == second[j - 1] ? 0: 1;

T[i][j] = std::min(std::min(T[i-1][j] + 1, T[i][j-1] + 1), T[i-1][j-1] + weight);

}

return T[m][n];

}

double findStringSimilarity(std::string first, std::string second) {

double max_length = std::max(first.length(), second.length());

if (max_length > 0) {

return (max_length - getEditDistance(first, second)) / max_length;

}

return 1.0;

}

int main() {

double similarity = findStringSimilarity("std::string", "C-string");

std::cout << similarity; // 0.545455

}

Download Run Code

That’s all about finding similarities between two strings in C++.

Find similarity between two strings in C++

Share this: