Palindromic SubsequencesProblem code: CB03 |
The problem is very simple. For every string given as input, you need to tell us the number of subsequences of it that are palindromes (need not necessarily be distinct). Note that the empty string is not a palindrome. For example, the palindromic subsequences of "aab" are: "a", "a", "b", "aa", and the method returns 4.
Input
First line contains the number of test cases T (atmost 20). Each of the next T lines contains a single string whose number of palindromic subsequences are to be printed. The maximum length of any input string is 50.
Output
For each test case, print in a single line, the number of palindromic subsequences of the input string.
Example
Input: 3 aab dddd thisisapalindromeemordnilapasisiht Output: 4 15 814157
| Author: | moneymachine |
| Date Added: | 16-01-2010 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
i cnt make out the 15
i cnt make out the 15 palindromic subsequences of 'dddd'. could someone pls help...
for 'dddd' there are 2^4-1
for 'dddd' there are 2^4-1 non-empty subsequence and each such subsequence is a palindrome.
Guys I want to know that will
Guys I want to know that will your Proagram works for longer Strings
like:
abcdefghijklmnopqrstuvwxyzthisisapalindromeemordnilapasisihtzyxwvutsrqponmlkjihgfedcba
Pls find the no of pallindromes in this String