Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1558
A palindorme is a sequence of one or more characters that reads the same from the left as it does from the right. For example, Z, TOT and MADAM are palindromes, but ADAM is not. Given a sequence S of N capital latin letters. How many ways can one score out a few symbols (maybe 0) that the rest of sequence become a palidrome. Varints that are only different by an order of scoring out should be considered the same. Input The input file contains several test cases (less than 15). The first line contains an integer T that indicates how many test cases are to follow. Each of the T lines contains a sequence S (1 ≤ N ≤ 60). So actually each of these lines is a test case. Output For each test case output in a single line an integer — the number of ways.
Sample Input 3 BAOBAB AAAA ABA
Sample Output 22 15 5
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
string in;
scanf("%d\n",&t);
while(t--){
getline(cin,in);
vector < vector<long long>> dp(in.length(),vector < long long>(in.length()));
for(int i=0;i < in.length();i++) dp[i][i] = 1;
for(int start=in.length()-1;start>=0;start--){
for(int end=start+1;end i+It in.length();end++){
if(in[start]==in[end]) // include this as palindrome, already double counted
dp[start][end] = dp[start][end-1] + dp[start+1][end] + 1;
else // double counted [start+1][end-1], need to remove overlap
dp[start][end] = dp[start][end-1] + dp[start+1][end] - dp[start+1][end-1];
}
}
printf("%lld\n",dp[0].back());
}
}
Input
BAOBAB
AAAA
ABA
Output
15
5
Demonstration
UVA Online Judge solution - 10617-Again Palindrome - UVA Online Judge solution in C,C++,java