字符串的回文子序列個數

Problem statement:

問題陳述：

Given a string you have to count the total number of palindromic subsequences in the giving string and print the value.

給定一個字符串，您必須計算給定字符串中回文子序列的總數并打印該值。

    Input:
T Test case
T no of input string will be given to you.
E.g.
3
abc
aa
abcc
Constrain 
1≤ length (string) ≤100
Output:
Print the count of the palindromic sub sequences from the given string.

Example

例

    T=3
Input:
abc
Output:
3 ("a", "b", "c")
Input:
aa
Output:
3 ("a", "a", "aa")
Input:
abcc
Output:
5 ("a", "b", "c", "c", "cc")

Explanation with example:

舉例說明：

Let there is a string str.

讓我們有一個字符串str 。

Now possible arrangements are:

現在可能的安排是：

1. Single middle characters like aba

   像aba這樣的單個中間字符

2. Paired middle characters like bb

   配對的中間字符，如bb

Let, f(a,b) = count of number of palindromic subsequences from index a to index b.

設f(a，b)=從索引a到索引b的回文子序列數。

Considering the above two facts:

考慮以上兩個事實：

1. If there is only one character then f(a,a) = 1

   如果只有一個字符，則f(a，a)= 1

2. If there is a substring starting from index a to index b then,

   如果存在從索引a到索引b的子字符串，

   1. If str[a] and str[b] both are same thenf(a,b)=f(a+1,b)+f(a,b-1)+1
   2. 如果str [a]和str [b]都相同，則f(a，b)= f(a + 1，b)+ f(a，b-1)+1
   3. If str[a] and str[b] both are not same thenf(a,b)=f(a+1,b)+f(a,b-1)-f(a+1,b-1)
   4. 如果str [a]和str [b]都不相同，則f(a，b)= f(a + 1，b)+ f(a，b-1)-f(a + 1，b-1)

For, str = abbaa

對于， str = abbaa

From the above, it is understandable that one function is called repeatedly so for the large input the repetition will be very high. Because of this problem we are using a Dynamic programming approach to avoid repetition. We are using the memorization process to solve the problem.

從以上內容可以理解，一個函數被重復調用，因此對于大的輸入，重復率會很高。 由于這個問題，我們使用動態編程方法來避免重復。 我們正在使用記憶過程來解決問題。

Problem solution:

問題方案：

Recursive algorithm:

遞歸算法：

int Function(str,pos,l):
if str.length()== l
return
for a=pos to str.length()-l 
if str[a]==str[a+l-1]
return Function(str,a,l-1)+Function(str,a+1,l-1)+1
else
return Function(str,a,l-1)+Function(str,a+1,l-1)-Function(str,a+1,l-2)

DP conversion:

DP轉換：

int Function(str,n):
for len=1 to str.length()
for a=0 to str.length()-len
b=pos+len-1
if str[a]==str[b]
arr[a][b]=arr[a+1][b]+ arr[a][b-1]+1
else
arr[a][b]=arr[a+1][b]+arr[a][b-1]-arr[a+1][b-1]
return arr[0][len-1]

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int count_palindrome(string str)
{
int len = str.length();
int arr[len][len] = { 0 };
for (int i = 0; i < len; i++) {
arr[i][i] = 1;
}
for (int l = 2; l <= len; l++) {
for (int i = 0; i <= len - l; i++) {
int j = i + l - 1;
if (str[i] == str[j]) {
arr[i][j] = arr[i + 1][j] + arr[i][j - 1] + 1;
}
else {
arr[i][j] = arr[i + 1][j] + arr[i][j - 1] - arr[i + 1][j - 1];
}
}
}
return arr[0][len - 1];
}
int main()
{
int t;
cout << "Test Case : ";
cin >> t;
while (t--) {
cout << "Enter the string : ";
string str;
cin >> str;
cout << "Number of palindromic subsequences are : " << count_palindrome(str) << endl;
}
return 0;
}

Output

輸出量

Test Case : 3
Enter the string : abc
Number of palindromic subsequences are : 3
Enter the string : aaa
Number of palindromic subsequences are : 7
Enter the string : abcc
Number of palindromic subsequences are : 5

翻譯自: https://www.includehelp.com/icp/count-the-number-of-palindromic-subsequences-in-a-given-string.aspx

字符串的回文子序列個數