C++에서 주어진 문자열의 모든 회문 하위 시퀀스 계산

이 튜토리얼에서는 주어진 문자열에서 모든 회문 부분 시퀀스의 수를 찾는 프로그램에 대해 논의할 것입니다.

이를 위해 문자열이 제공됩니다. 우리의 임무는 주어진 문자열에서 만들 수 있는 회문 부분 시퀀스의 수를 찾는 것입니다.

예시

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

출력

Total palindromic subsequence are : 6