C++ 通过设置仅有一个K大小的子字符串位来最小化二进制字符串的海明距离

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

S= “ramanisgoing”

T= “dishaisgoing”

在这里，字符串S和T之间的海明距离为5，因为raman和disha是使得字符串不同而变得相等的两个单词。

问题陈述

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

让我们通过一些示例来了解这个问题。

输入 - S = “100111”，K = 5

输出 - 3

解释 - 初始字符串T将等于”000000″，当k=5时，字符串T将改变以与字符串S进行比较以找到最小的海明距离，结果如下：”111110″和”011111″。

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

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

输入 - S = “100101”，K = 5

输出 - 3

解释 - 初始字符串T将等于”000000″，当k=5时，字符串T将改变以与字符串S进行比较以找到最小的海明距离，结果如下：”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 个不同子字符串之间的 1 的值。
如果(i-1<0)，将值 v 作为 arr[i+K-1]，否则将值 v 作为(arr[i+K-1]-arr[i-1])。
通过找到前一个汉明距离和当前汉明距离之间的最小值来存储最小值。
当前汉明距离可以通过对 K 子字符串中的零元素数目进行处理（K-v）和当前 S 子字符串中的零数目（cnt-v）来计算得出。
最后，返回总体最小距离。

示例

下面是上述方法的 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;
}