asp网站优化访问速度,做淘宝网站多少钱,什么是开放式的网站,网站建设案例 星座字符串的回文子序列个数Problem statement: 问题陈述#xff1a; Given a string you have to count the total number of palindromic subsequences in the giving string and print the value. 给定一个字符串#xff0c;您必须计算给定字符串中回文子序列的总数并打印该值…字符串的回文子序列个数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 例 T3
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: 现在可能的安排是 Single middle characters like aba 像aba这样的单个中间字符 Paired middle characters like bb 配对的中间字符如bb Let, f(a,b) count of number of palindromic subsequences from index a to index b. 设f(ab)从索引a到索引b的回文子序列数。 Considering the above two facts: 考虑以上两个事实 If there is only one character then f(a,a) 1 如果只有一个字符则f(aa) 1 If there is a substring starting from index a to index b then, 如果存在从索引a到索引b的子字符串 If str[a] and str[b] both are same thenf(a,b)f(a1,b)f(a,b-1)1 如果str [a]和str [b]都相同则f(ab) f(a 1b) f(ab-1)1 If str[a] and str[b] both are not same thenf(a,b)f(a1,b)f(a,b-1)-f(a1,b-1) 如果str [a]和str [b]都不相同则f(ab) f(a 1b) f(ab-1)-f(a 1b-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 apos to str.length()-l
if str[a]str[al-1]
return Function(str,a,l-1)Function(str,a1,l-1)1
else
return Function(str,a,l-1)Function(str,a1,l-1)-Function(str,a1,l-2)
DP conversion: DP转换 int Function(str,n):
for len1 to str.length()
for a0 to str.length()-len
bposlen-1
if str[a]str[b]
arr[a][b]arr[a1][b] arr[a][b-1]1
else
arr[a][b]arr[a1][b]arr[a][b-1]-arr[a1][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字符串的回文子序列个数
