এই টিউটোরিয়ালে আমরা একটি দেওয়া স্ট্রিং-এ সব প্যালিনড্রোমিক সাবসিকোয়েন্সের সংখ্যা বের করার প্রোগ্রাম নিয়ে আলোচনা করব।
এই জন্য আমাদের একটি স্ট্রিং দেওয়া থাকবে। আমাদের কাজ হলো দেওয়া স্ট্রিং-এ কতগুলো প্যালিনড্রোমিক সাবসিকোয়েন্স তৈরি করা যায় সেটা বের করা।
উদাহরণ
#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
