Palindromic substring query in C++

In this tutorial, we need to solve the palindromic substring query of a given string. Solving palindrome substring queries is much more complex than solving regular queries in C. It requires more complex code and logic.

In this tutorial, we have provided string str and Q substring [L...R] queries, each with two values ​​L and R. Our goal is to write a program that solves a query to determine whether substring[L...R] is a palindrome. We must determine whether the substring formed in the range L to R is a palindrome to solve each query. For example-

Let's input "abbbabaaaba" as our input string.
The queries were [3, 13], [3, 11], [5, 8], [8, 12]
It is necessary to determine whether the substring is a plaindrome
A palindrome is "abaaabaaaba" (3, 13) .
It is not possible to write "baaa" as a palindrome [3, 11].
As in [5, 8]: "aaab" cannot be a palindrome.
There is a palindrome in "baaab" ([3, 12]).

Solution method

Naive method

Here, we have to check whether the substring is between the index range L to R To find palindromes, therefore, we need to check all substring queries one by one to determine whether they are palindromes. Since there are Q queries, each query takes 0(N) time to answer. It takes 0(Q.N) time in the worst case.

Example

#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
   int i, length;
   int flag = 0;
   length = str.length();
   for(i=0;i < length ;i++){
      if(str[i] != str[length-i-1]) {
         flag = 1; break;
      }
   }
   if (flag==1)
      return 1;
   return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
   for(int i = 0; i < Q; i++){
      isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))? cout<<"Palindrome\n":cout<<"Not palindrome!\n";
   }
}
int main() {
   string str = "abccbeba"; int Q = 3;
   int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
   solveAllQueries(str, Q, query);
   return 0;
}

Output

Palindrome
Palindrome
Not palindrome!

Dynamic programming method

Using dynamic programming method to solve the problem is an effective option. To solve this problem, we need to create a DP array, which is a two-dimensional array that contains a boolean value indicating whether substring[i...j] is a palindrome of DP[i][j].

This DP matrix will be created and all L-R values ​​for each query will be checked.

Example

#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
   int length = str.size();
   int i, j;
   for (i = 0; i < length; i++) {
      for (j = 0; j < length; j++)
         DP[i][j] = 0;
   }
   for (j = 1; j <= length; j++) {
      for (i = 0; i <= length - j; i++) {
         if (j <= 2) {
            if (str[i] == str[i + j - 1])
               DP[i][i + j - 1] = 1;
         }
         else if (str[i] == str[i + j - 1])
            DP[i][i + j - 1] = DP[i + 1][i + j - 2];
      }
   }
}
void solveAllQueries(string str, int Q, int query[][2]){
   int DP[50][50];
   computeDP(DP, str);
   for(int i = 0; i < Q; i++){
      DP[query[i][0] - 1][query[i][1] - 1]?cout
      <<"not palindrome!\n":cout<<"palindrome!\n";
   }
}
int main() {
   string str = "abccbeba"; int Q = 3;
   int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
   solveAllQueries(str, Q, query);
   return 0;
}

Output

palindrome!
not palindrome!
palindrome!

Conclusion

In this tutorial, we learned how to solve a palindrome substring query using C code. We can also write this code in java, python and other languages. This code is one of the most complex and verbose. Palindrome queries are more difficult than regular substring queries and require very precise logic. We hope you found this tutorial helpful.

The above is the detailed content of Palindromic substring query in C++. For more information, please follow other related articles on the PHP Chinese website!