Đếm tất cả chuỗi con Palindromic trong một chuỗi nhất định 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ố lượng của tất cả các chuỗi con palindromic trong một chuỗi nhất định.

Đố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à tìm số lượng chuỗi con palindromic có thể được tạo trong chuỗi đã cho đó.

Ví dụ

#include<iostream>
#include<cstring>
using namespace std;
//returning total palindromic sequence
int count_palin(string str){
   int N = str.length();
   //creating a 2D array
   int cps[N+1][N+1];
   memset(cps, 0 ,sizeof(cps));
   for (int i=0; i<N; i++)
      cps[i][i] = 1;
   for (int L=2; L<=N; L++){
      for (int i=0; i<N; i++){
         int k = L+i-1;
         if (str[i] == str[k])
            cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;
         else
            cps[i][k] = cps[i][k-1] + cps[i+1][k] - cps[i+1][k-1];
      }
   }
   return cps[0][N-1];
}
int main(){
   string str = "abcb";
   cout << "Total palindromic subsequence are : " << count_palin(str) << endl;
   return 0;
}

Đầu ra

Total palindromic subsequence are : 6