透過設定僅包含K個位的子字串，將二進位字串的漢明距離最小化

兩個等長字串之間的漢明距離是對應位置上存在不同值的所有位置的數量。我們可以透過下面的範例來理解：

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

• 透過尋找前一個漢明距離和目前漢明距離之間的最小值來儲存最小值。

• 目前的漢明距離可以透過對(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;
}

輸出

The minimum hamming distance is: 3

結論

在本文中，為了找到最小的漢明距離，我們首先會看到一種簡單的方法，但為了改進其時間複雜度，我們將使用前綴和數組的概念，透過它我們可以在一個循環中避免重複計數。

以上是透過設定僅包含K個位的子字串，將二進位字串的漢明距離最小化的詳細內容。更多資訊請關注PHP中文網其他相關文章！