学步园

/*
 * =====================================================================================
 *
 *       Filename:  panguo1.c
 *
 *    Description:  求一个序列的子序列个数,重复的不计,如:a ,子序列个数1, aa,2; ab,3;
 *
 *        Version:  1.0
 *        Created:  2013年09月21日 01时02分54秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ni WenXian (hello world~ iam coming), niwenxianq@qq.com
 *   Organization:  AMS/ICT
 *
 * =====================================================================================
 */

#include <iostream>
#include <cstring>
using namespace std;
int subset(char * str, int len)
{
    if(len == 0 || len == -1)
    return 0;
    if(len == 1 )
    return 1;
    if(len == 2 && str[0]==str[1])
    return 2;
    if( len==2 && str[0]!=str[1] )
    return 3;
    int flag=-1;
    int i;
    for(i=1;i<len;i++)
    {
        if(str[len-i-1]==str[len-1])
        {
        flag = len-i-1;
        break;
        }
        else
        continue;
    }
    if(flag == -1)
        return 2*subset(str, len-1) +1;
    else
        return 2*subset(str, len-1) - subset(str, flag);
}
int main()
{
    int tcase;
    int len;
    char str[1000];
    cin>>tcase;
    while(tcase--)
    {
        cin>>str;
        len = strlen(str);
        cout<<"len = "<<len<<endl;
        cout<<subset(str, len)<<endl;
    }
    return 0;
}