encode.cpp

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小 写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到 右出现的次序与字母在字母

/************************************************************************/
/* 字典序问题  2008.3.12 by JackyGao                                    */
/************************************************************************/
#include <iostream>
using namespace std;
//////////////////////////////////////////////////////////////////////////

/************************************************************************/
/*以第i个字符打头的长度不超过k的升序字符串个数                          */
/************************************************************************/
int f(int i , int k);

/************************************************************************/
/*长度不超过k的升序字符串总个数                                         */
/************************************************************************/
int g(int k);

/************************************************************************/
/* 判断长度为len的输入字符串input是否合法                               */
/************************************************************************/
bool check(char * input, int & len);


int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int i , 
		j , 
		k , 
		m ,
		count ,
		len ,
		sum = 0;
	char input[7];
	int code[7];
	code[0] = 0;
	cin >> count;
	for (i = 0 ; i < count ; i ++)
	{
		cin >> input;
		//cout << input << endl;// check the input
		len = strlen(input);
		if (!check(input , len))//illegal input
		{
			cout << 0 << endl;
		} 
		else//legal input
		{
			sum = 0;
			for (j = 1 ; j <= len ; j ++)
			{
				code[j] = input[j-1] - 'a' + 1;//a=1,b=2...
			}
			for (j = 1 ; j < len ; j ++)
			{
				sum = sum + g(j);
			}
			for( k = 1 ; k <= len ; k ++)
			{
				for(m = code[k-1] + 1 ; m <= code[k] - 1 ; m ++)
				{
					sum = sum + f(m , len - k + 1);
				}
			}
			cout << sum + 1 << endl;
		}
		

	}
	return 0;
}


/************************************************************************/
/*以第i个字符打头的长度不超过k的升序字符串个数                          */
/************************************************************************/
int f(int i , int k)
{
	int j , sum = 0;
	if (k == 0)//wrong input
	{
		return 0;
	}
	if (k == 1)//right input
	{
		return 1;
	} 
	else
	{
		for (j = i + 1 ; j <= 26 ; j ++)
		{
			sum = sum + f(j , k - 1);
		}
		return sum;
	}
	return -1;
}


/************************************************************************/
/*长度不超过k的升序字符串总个数                                         */
/************************************************************************/
int g(int k)
{
	
	switch(k)//optimized for this problem
	{
	case 1:
		return 26;
		break;
	case 2:
		return 325;
		break;
	case 3:
		return 2600;
	    break;
	case 4:
		return 14950;
	    break;
	case 5:
		return 65780;
	    break;
	default:
		break;
	}
	int i;
	int sum = 0;
	for (i = 1 ; i <= 26 ; i ++)
	{
		sum = sum + f(i , k);
	}
	return sum;
}

/************************************************************************/
/* 判断长度为len的输入字符串input是否合法                               */
/************************************************************************/
bool check(char * input, int & len)
{
	for (int i = 1 ; i < len ; i ++)
	{
		if (input[i]<=input[i-1])
		{
			return false;
		}
	}
	return true;
}