在本教程中,我们将讨论一个程序,以查找给定字符串中所有回文子序列的数量。
为此,我们将提供一个字符串。我们的任务是找到在给定字符串中可以回文的子序列的数量。
#include<iostream> #include<cstring> using namespace std; //返回总回文序列 int count_palin(string str){ int N = str.length(); //创建一个二维数组 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 << "回文总子序列为: " << count_palin(str) << endl; return 0; }
输出结果
回文总子序列为: 6