C++ 三个非重叠子字符串的拼接构成回文串的数量

介绍

在本教程中，我们将详细说明一种从给定字符串s中找到三个非重叠子字符串的方法，并且当所有子字符串组合在一起时它们形成一个回文串。为了解决这个任务，我们使用C++编程语言的字符串类特性。

字符串中的回文串意味着字符串在正向和反向方向上都读起来相同。回文串的示例是Madam。

假设有一个字符串“s”和子字符串是a、b和c。当你将a、b和c组合在一起时，它们形成一个回文串。以下是一个示例来理解问题逻辑。

问题说明

String s = “abbacab”      
Acceptable substrings of length 3 are: “abb”, “bac”, and “bba”.

将三个子字符串连接起来得到的字符串是一个回文字符串，该字符串为abbbacbba。

语法

size()函数属于string类，用于获取输入字符串的大小，即字符长度。

string_name,size();

步骤

• 接受一个输入字符串。

• 初始化一个计数器变量，用于记录回文子串的数量。

• 使用三层嵌套的循环生成三种可能的子串。

• 第一个内循环初始化为0至字符串长度-3。

• 第二个内循环初始化为第一个内循环+1至字符串长度-2。

• 外循环初始化为第二个循环+1至字符串长度-1。

• 找到所有子串后，将它们连接起来。

• 检查是否存在子串回文，如果是，则增加计数器变量的值。

• 打印计数器变量的值。

示例

要使用C++实现上述算法，我们使用一个输入字符串，生成所有可能的子串组合，只考虑那些是回文的子串。如果存在这样的子串，计数器变量将增加。打印计数器变量的结果。

#include <bits/stdc++.h>
using namespace std;

// user defined function to check formed substrings are palindrome or not
bool isStringPalin(int a, int b, int c, int d, int x, int y, string st){
   int begin = a, stop = y;
   while (begin < stop) {
      if (st[begin] != st[stop])
         return false;

      begin++;
      if (begin == b + 1)
         begin = c;
      stop--;
      if (stop == x - 1)
         stop = d;
   }
   return true;
}

// User defined function to count the number of useful substrings
int countSubString(string st){
   //Counting variable to count and return the number of substrings
   int ct = 0;
   int l = st.size();

   //It is to select the first substring
   for (int a = 0; a < l - 2; a++) {
      for (int b = a; b < l - 2; b++){

         // This loop selects the second useful substring
         for (int c = b + 1; c < l - 1; c++) {
            for (int d = c; d < l - 1; d++) {

               // this for loop will select the third substring
               for (int x = d + 1; x < l; x++) {
                  for (int y = x; y < l; y++) {

                     // If condition to check the selected substrings are forming palindrome or not
                     if (isStringPalin(a, b, c, d, x, y, st)) {
                        ct++;
                     }
                  }
               }
            }
         }
      }
   }
   // returning the count variable that stores the number of useful substrings
   return ct;
}

// Controlling code
int main(){
   string st = "abcab";
   cout << "The possible number of substrings are: "<< countSubString(st);

   return 0;
}

输出

The possible number of substrings are: 4

结论

我们开发了一种寻找形成回文子串的有效子串的方法。为了实现解决方案，我们使用C++循环和if条件。为了使用C++实现其中一个示例，我们使用了size()函数和嵌套循环。嵌套循环有助于找到不同长度的子串，而size()函数返回字符串的大小。