2015
09-17

# Palindrome subsequence

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence <A, B, D> is a subsequence of <A, B, C, D, E, F>.
(http://en.wikipedia.org/wiki/Subsequence)

Given a string S, your task is to find out how many different subsequence of S is palindrome. Note that for any two subsequence X = <Sx1, Sx2, …, Sxk> and Y = <Sy1, Sy2, …, Syk> , if there exist an integer i (1<=i<=k) such that xi != yi, the subsequence X and Y should be consider different even if Sxi = Syi. Also two subsequences with different length should be considered different.

The first line contains only one integer T (T<=50), which is the number of test cases. Each test case contains a string S, the length of S is not greater than 1000 and only contains lowercase letters.

The first line contains only one integer T (T<=50), which is the number of test cases. Each test case contains a string S, the length of S is not greater than 1000 and only contains lowercase letters.

4
a
aaaaa
goodafternooneveryone
welcometoooxxourproblems

Case 1: 1
Case 2: 31
Case 3: 421
Case 4: 960

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
char s[maxn];
int main(){
int t;
int ca = 1;
scanf("%d",&t);
while(t --){
scanf("%s",s);
int len = strlen(s);
for(int l = 0;l < len;l ++){
for(int i = 0;i + l < len;i ++){
if(l == 0)dp[i][i] = 1;
else if(l == 1){
if(s[i] == s[i + 1])dp[i][i + 1] = 3;
else dp[i][i + 1] = 2;
}
else {
dp[i][i + l] = dp[i + 1][i + l] + dp[i][i + l - 1] - dp[i + 1][i + l - 1];
if(s[i] == s[i + l])dp[i][i + l] += dp[i + 1][i + l - 1] + 1;
dp[i][i + l] = (dp[i][i + l] + 10007) % 10007;
}
//printf("i = %d j = %d dp = %d\n",i,i + l,dp[i][i + l]);
}
}
printf("Case %d: %d\n",ca ++,dp[0][len - 1]);
}
return 0;
}