將字串對拼接後包含“string”中所有字元的字串對

---

簡介

一系列字元流一起構成，包含字母數字字元以及特殊符號，可以稱為C++字串。

字串拼接是字串資料結構的一個重要方面，因為它用於組合不同的子字串或單詞以形成完整的句子。在C++中，拼接可以使用+運算子簡單地完成。在本文中，我們將開發一個程式碼，該程式碼將字串陣列作為輸入，然後分析每一對以檢視該對是否包含單詞“string”的所有字母。讓我們來看下面的例子，以便更好地理解這個主題。

示例

示例1：

str − {"rtsr", "string", "gin","strin"}
Output − 5

在下面的示例中，共有5對包含單詞string的所有字母：

{rtsr , string} , {rtsr , gin } , {string , strin } , {string , gin } , {gin , strin }

在本文中，我們將開發一個程式碼來處理輸入陣列中的對，這些對以位掩碼的形式出現，這些位掩碼對應於單詞“string”的字元。由於單詞“string”共有6個字元，因此組合總數等於2^6-1，即63。

語法

str.length()

length()

每個C++字串都由固定數量的字母數字字元組成。C++中的length()方法用於計算字串中的字元數。

sizeof(obj)

sizeof()

sizeof()方法用於返回呼叫此方法的物件分配的位元組數。由於1位元組，返回的大小是以字元變數大小的倍數形式返回的。

演算法

• 接受一個字串輸入陣列arr。

• 使用length()方法計算字串的長度，並將其儲存在len變數中。

• 單詞“string”的長度為6，因此可以生成0-63的布林組合。

• 將對應於此陣列arr的每個字串儲存為其位掩碼。

• 儲存MAX值以保留位掩碼的總數。

• 如果訪問的arr字串中的字元包含在“string”中，則將其對映到值1，否則為0。例如，“srng”對映到101011。

• 計算每個字串的位掩碼後，獨立分析每一對。

• maski對應於第i個字串的掩碼，maskj對應於第j個字串的掩碼。如果兩個字串的位掩碼組合為63（111111），則表示該對中存在單詞string的所有字母。

• 如果i和j相等，則計數增加(maski *maski -1)/2。否則，計數增加(maski *maskj)。

• 然後返回計數。

示例

以下C++程式碼片段用於將字串陣列作為輸入，然後評估包含單詞“string”的所有字元的所有對計數：

#include <bits/stdc++.h>
using namespace std;
#define MAX 64
 
// Function to return the bitmask for the string
int masking(string str) {
   int len = str.length();
   int temp = 0;
   for (int j = 0; j < len; j++) {
      char ch = str[j];
      //if character equals s
      if (ch == 's') {
         temp = temp | (1);
      }
      //if equals t
      else if (ch == 't') {
         temp = temp | (2);
      }
      //if equal r
      else if (ch == 'r') {
          temp = temp | (4);
      }
      //if equals i 
      else if (ch == 'i') {
          temp = temp | (8);
      }
      else if (ch == 'n') {
          temp = temp | (16);
      }
      else if (ch == 'g') {
         temp = temp | (32);
      }
   } 
   return temp;
}
 
// Function to return the count of pairs
int pairswithString(string arr[], int n) {
   int cnt = 0;
   // bitMask[i] will store the count of strings whose bitmask is i
   int bit[64] = { 0 };
    
   for (int i = 0; i < n; i++)
      bit[masking(arr[i])]+=1;
 
   //looping through the maskings obtained
   for (int i = 0; i < MAX; i++) {
      for (int j = i; j < MAX; j++) {
         // MAX - 1 = 63 
         if ((i | j) == (MAX - 1)) {
            int maski = bit[i];
            int maskj = bit[j];
            //any element cannot be a pair with itself
            if (i == j)
               cnt += ((maski * maski - 1) / 2);
            else
               cnt += ( maski * maskj );
         }
      }
   }
   return cnt;
}
 
int main() {
   string arr[] = { "rtsr", "string", "gin","strin" };
   cout<<"Input array ";
   for(string s : arr)
      cout<<s<<"\n";
   int len = sizeof(arr) / sizeof(arr[0]);
   int count = pairswithString(arr, len);
   cout<< "Total count of pairs : "<<count<<"\n";
 
   return 0;
}

輸出

Input array rtsr
string
gin
strin
Total count of pairs − 5

結論

位掩碼可以很容易地用於操作和分析字串。然後可以評估位掩碼以檢視它們的組合是否匹配，然後可以透過(n * n-1)/2來評估直到數字n的總和；