Compute three non-overlapping substrings and concatenate them to form a palindrome

Introduction

In this tutorial, we will elaborate on a method to find three non-overlapping substrings from a given string s, and when all substrings are combined together, they form a palindrome. To solve this task, we use the string class functionality of C programming language.

A palindrome in a string means that the string reads the same in both forward and backward directions. An example of a palindrome string is Madam.

Suppose there is a string "s", and the substrings are a, b, c. When you combine a, b, and c, they form a palindrome string. This is an example of understanding the logic of the problem.

Statement explanation

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

When we concatenate all three substrings, the resulting string is a palindrome string, which is abbbacbba.

grammar

size() function belongs to the string class and is used to obtain the size of the input string and its character length.

string_name,size();  

algorithm

• Get the input string.

• Initialize a counter variable used to track the number of palindrome substrings.

• Use 3 nested for loops to generate 3 possible substrings of defined length.

• The first inner loop is initialized from 0 to string length - 3.

• The second inner loop is initialized from the first inner loop 1 to the string length - 2.

• The outer loop is initialized from the second loop 1 to the string length - 1.

• After finding all substrings, concatenate them.

• Check whether there is a substring palindrome, and if so, increment the counter variable value.

• Print counter variable value.

Example

To implement the above algorithm using C, we take the input string and generate all possible combinations of substrings and consider only those palindromic substrings. If such a substring is possible, the counter variable will be incremented. Print the result of the counter variable.

#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;
}

Output

The possible number of substrings are: 4

in conclusion

We developed a method to find valid substrings that form palindromes. To implement this solution, we used C loops and if conditions. To implement one of the examples in C, we used the size() function and nested loops. Nested loops help to find substrings of different lengths and the size() function returns the size of the string.

The above is the detailed content of Compute three non-overlapping substrings and concatenate them to form a palindrome. For more information, please follow other related articles on the PHP Chinese website!