将字符串对拼接后包含“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的总和；