通过设置仅包含K个位的子字符串，将二进制字符串的汉明距离最小化

王林转载: 2023-09-18 13:09:03 368浏览

两个等长字符串之间的汉明距离是在对应位置上存在不同值的所有位置的数量。我们可以通过下面的示例来理解：

S= “ramanisgoing”

的中文翻译为：

S= “ramanisgoing”

T=“dishaisgoing”

这里，5 是两个字符串 S 和 T 之间的汉明距离，因为 raman 和 disha 是两个使字符串中的差异变得相等的单词。

问题陈述

然而，在这个问题中，我们需要找到仅包含二进制数字的两个字符串之间的汉明距离。一个字符串将由用户提供，假设为S，另一个字符串，假设为T，最初，我们假设它只包含'0'位，并且与给定字符串的大小相等。我们将得到一个数字'k'，其值表示一个子字符串可以由仅为其元素的'1'组成的元素数量，以便我们将该大小为k的子字符串放在字符串(T)的任何位置，以最小化两个子字符串S和T之间的汉明距离。

让我们通过一些例子来尝试理解这个问题。

输入 − S = "100111” K = 5

输出 - 3

Explanation − 初始字符串 T 等于“000000”，并且字符串 T 会被改变以与字符串 S 进行比较，以找到 k=5 时的最小汉明距离，如下所示：“111110”和“011111”。

100111和000000的海明距离为4。100111和111110的海明距离为3，而100111和011111的海明距离也为3。

但是最小的汉明距离将为3，因为3小于4。因此，我们的答案是3。

- S =“100101”K = 5

- 3

− 作为初始字符串T将等于“000000”，并且字符串T将被更改以与字符串S进行比较，以找到k=5时的最小汉明距离，如下所示：“111110”和“011111”。

100101和000000的汉明距离为3。100101和111110的汉明距离为4，而100101和011111的汉明距离也为4。

但是最小的汉明距离将为3，因为3小于4。因此，我们的答案是3。

问题解释

让我们试着理解这个问题并找到解决办法。

解决方案1 暴力解决方案

我们将通过改变不同初始和结束点的子字符串的位置来修改字符串T，以便在所有可能的字符串中获得最小的汉明距离。

示例

下面是上述方法的C++程序实现：

#include <bits/stdc++.h>
using namespace std;
// Make a function to get minimum hamming distance through iteration
int helper(string S,int k){
   // n is the size of the string
   int n=S.size();
   // Take another string T and initiate it with zero bits size equal to that of S
   string T;
   for(int i=0;i<n;i++){
      T+="0";
   }
   // Take another string v to initiate it same as T
   string v=T;
   // Define mini as the hamming distance between T and S
   int mini=0;
   int l=0; 
   while(l<n){
      if(S[l]!=T[l])mini++;
         l++;
   }
   for(int i=0;i<n-k+1;i++){
      int j=0,a=0,l=0;
      // alter string v by changing bits of size k
      while(j<k){
          v[j+i]='1';
          j++;
      }
      // calculate hamming distance
      while(l<n){
         if(S[l]!=v[l])a++;
           l++;
      }
      // Check if the previous hamming distance is greater than the current hamming distance, if yes then replace that distance element
      if(mini>a){
         mini=a;
      }
      // Again assign v as the T string
      v=T;
    }
    // return the minimum hamming distance found through the above iterations
    return mini;
}
int main() {
   // Give input string S
   string S = "100101";
   // Give the value of k that is the substring size
   int K = 5;
   // Call the helper function
   cout << "The minimum hamming distance is: "<< helper(S,K);
   return 0;
}

输出

The minimum hamming distance is: 3

解决方案2 优化方案

算法

使用前缀和数组计算1的数量，并将其存储为我们的最小汉明距离
遍历字符串S以找到字符串S中K个不同子字符串之间的值。
如果(i-1<0)，则将值v作为arr[i+K-1]，否则将值v作为(arr[i+K-1]-arr[i-1])
通过查找前一个汉明距离和当前汉明距离之间的最小值来存储最小值。
当前的汉明距离可以通过对(K - v)子字符串中零元素的数量和当前S子字符串中零的数量进行操作来找到
最后，返回整体最小距离。

示例

下面是上述方法的C++程序实现

#include <bits/stdc++.h>
using namespace std;
// Make a helper function to get minimum hamming distance through iteration
int helper(string S, int K){
 // n is the size of the string
	int n = S.size();
	// initialize an array of size 'n'
	int arr[n];
	if(S[0]=='0')arr[0]=0;
	else arr[0]=1;
	// Count the number of 1's in the string S
	for (int i = 1; i < n; i++){
	    if(S[i]=='0')arr[i]=arr[i-1];
	    else arr[i]=arr[i-1]+1;
	}
	int cnt = arr[n - 1];	
	// Define mini as the hamming distance between T and S
	int mini = cnt;
	// Traverse through S to find the minimum
	for (int i = 0; i < n - K; i++) {
		int v;
		if(i-1==-1)v=arr[i+K-1];
		else v= arr[i+K-1]-arr[i-1];
		// Store the minimum
		mini = min(mini, cnt - v + (K - v));
	}
    // Return the minimum hamming distance
	return mini;
}
int main(){
	// Give input string S
    string S = "100101";
    // Give the value of k that is the substring size
    int K = 5;
    // Call the helper function
    cout << "The minimum hamming distance is: "<< helper(S,K);
    return 0;
}