计算C ++中给定字符串中的所有回文子序列

在本教程中,我们将讨论一个程序,以查找给定字符串中所有回文子序列的数量。

为此,我们将提供一个字符串。我们的任务是找到在给定字符串中可以回文的子序列的数量。

示例

#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

以上是 计算C ++中给定字符串中的所有回文子序列 的全部内容, 来源链接: utcz.com/z/322455.html

回到顶部