Đếm tất cả các chuỗi con Palindrome trong một chuỗi trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số chuỗi con palindrome trong một chuỗi.

Đối với điều này, chúng tôi sẽ được cung cấp một chuỗi. Nhiệm vụ của chúng ta là đếm số chuỗi con palindrome trong chuỗi đã cho có độ dài lớn hơn 3.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
//counting palindrome strings
int count_pstr(char str[], int n){
   int dp[n][n];
   memset(dp, 0, sizeof(dp));
   bool P[n][n];
   memset(P, false , sizeof(P));
   for (int i= 0; i< n; i++)
      P[i][i] = true;
   for (int i=0; i<n-1; i++) {
      if (str[i] == str[i+1]) {
         P[i][i+1] = true;
         dp[i][i+1] = 1 ;
      }
   }
   for (int gap=2 ; gap<n; gap++) {
      for (int i=0; i<n-gap; i++) {
         int j = gap + i;
         //if current string is palindrome
         if (str[i] == str[j] && P[i+1][j-1] )
            P[i][j] = true;
         if (P[i][j] == true)
            dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];
         else
            dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
      }
   }
   return dp[0][n-1];
}
int main(){
   char str[] = "abaab";
   int n = strlen(str);
   cout << count_pstr(str, n) << endl;
   return 0;
}

Đầu ra

3