How to find Hamming distance between two strings in c++

Hello,
In this tutorial, we will learn how to find the hamming distance between two string in C++. Before that, let’s understand what is Hamming distance first.

Hamming distance

Hamming distance is the number of mismatched characters of two strings of equal length. or in theoretical aspect, we can say that Hamming distance is the result of XOR operation between two equal length strings.

The Hamming distance between two strings is represented by d(string1,string2).

let’s take a few examples to understand it in a better way:

Example 1:

consider string1 = "codespeedy" and string2 = "coodespedy"

If we compare the string1 and string2 we can find five different characters which are: 
"codespeedy" and "coodespedy"

Therefore, d(codespeedy,coodespedy) = 5

Example 2:

consider string1 = "100101011" and string2 = "110110010"

If we compare string1 and string2 we can find four different bits which are: 
"100101011" and "110110010"

Therefore, d(100101011, 110110010) = 4

Finding hamming distance between two string in C++

#include <cstdlib>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

int main(int argc, char** argv) {
    char string1[100], string2[100];  
    int count = 0;
    cout<<"Enter first string: ";
    gets(string1);                         //initializing string 1  
    cout<<"\nEnter second string: ";
    gets(string2);                         //initializing string 2
    
    if(strlen(string1) != strlen(string2))
    {
        cout<<"\n\nstring's length must be same.\n\n";
        exit(0);
    }
    
    //finding Hamming distance
    for(int i=0; string1[i]!=0; i++)
        if(string1[i] != string2[i])
            count++;
    cout<<"\nhamming Distance: "<<count;
    
    return 0;
}

Time complexity: O(n)




Explanation: 

line 8 – 13: In line 8, the two character type variables string1 and string2 having maximum size 100 is declared to store the two strings entered by the user.
Then in line 9, A integer type variable count is declared to store Hamming distance and initialized to zero to avoid garbage values.
Then using “gets()”, the two strings will be taken as input from output stream and stored in string1 and string2.

line 15 – 19: In order to find the Hamming distance, the two strings must be of the same length. Therefore in line 15, we are comparing the length of  string1 and string2. If the length of the two strings is not equal then it will exit the main by showing a message in the output – “string’s length must be same.

line 22 – 24: Here is the main logic of our program. A for loop which will repeat till the length of strings (as both the string have the same length) and inside the for loop the equality of each element of string1 is checked with string2. if the i’th element of string1 is not equal to the i’th element of string2 then count will be incremented by one.

Also, read:

 

line 25: After the termination of the loop, the value in the count will be the Hamming Distance. Therefore at line 25, Hamming distance between string1 and string2 is showing to the output string.


Leave a Reply

Your email address will not be published. Required fields are marked *