ในบทช่วยสอนนี้ เราจะอภิบายโปรแกรมเพื่อหาจำนวนซับซีเควลพาลินโดรมทั้งหมดในสตริงที่กำหนด
สำหรับเรื่องนี้ เราจะได้รับสตริง งานของเราคือหาจำนวนซับซีเควลพาลินโดรมที่สามารถทำได้ในสตริงที่กำหนด
ตัวอย่าง
#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
