10069.cpp

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define MAXN 10003

#define BASE   1000000
#define MAX_DIGIT  70
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

typedef long  long INT;

class BigNum
{
private:
    INT sign, len, digit[MAX_DIGIT];
    void absAdd(BigNum, BigNum);
 
public:
    void operator  = (INT);             //ok
    void operator  = (BigNum);          //ok
    void operator  = (char *);          //ok
    void add(BigNum, INT);              //ok-
    void add(BigNum, BigNum);           //ok-
    void print();                       //ok-
    void update();                      //ok-
    void clear();                       //ok-
    BigNum() {clear(); }
};

void BigNum :: operator = (INT x)		
{
    clear();
    if(x < 0)
    {
	x = -x;
	sign = 1;
    }
    if(x == 0)
    {
	digit[len++] = 0;
	return;
    }
    while(x)
    {
	digit[len++] = x % BASE;
	x /= BASE;
    }
}

void BigNum :: operator = (BigNum n)
{
    INT i;

    clear();
    len = n.len;
    sign = n.sign;
    for(i = 0; i < len; ++i)
    {
	digit[i] = n.digit[i];
    }
}

void BigNum :: operator = (char *s)
{
    INT i, v, p;

    clear();
    p = 1;
    i = strlen(s) - 1;
    for(v = 0; i >= 0; i--){
		if(s[i] == '-')	{
			--i;
			sign = 1;
			break;
		}
		else if(s[i] == '+'){
			--i;
			break;
		}
		if(s[i] < '0' || s[i] > '9' ) continue;
		v = v + (s[i] - '0') * p;
		p *= 10;
		if(p == BASE)
		{	
			digit[len++] = v;
			p = 1;
			v = 0;
		}
    }
    if(v)
    {
		digit[len++] = v;
    }
    update();
}

void BigNum::absAdd(BigNum a, BigNum b)
{
    INT pos, carry;

    carry = 0;
    for(pos = 0; pos < max(a.len, b.len); ++pos)
    {
	digit[pos] = a.digit[pos] + b.digit[pos] + carry;
	carry = digit[pos] / BASE;
	digit[pos] %= BASE;
    }
    if(carry != 0)
    {
	digit[max(a.len, b.len)] = carry;
	len = max(a.len, b.len) + 1;
    }
    else
    {
	len = max(a.len, b.len);
    }
    update();
}

void BigNum :: add(BigNum a, INT n)
{
    BigNum t;

    t = n;
    add(a, t);
}

void BigNum :: add(BigNum a, BigNum b)
{
    clear();
   	absAdd(a, b);
	sign = a.sign;
}




void BigNum :: update()
{
    while(len > 1 && digit[len - 1] == 0)
    {
	--len;
    }
    if(len <= 1 && digit[0] == 0)
    {
	sign = 0;
    }
}

void BigNum :: clear()
{
    sign = len = 0;
    memset(digit, 0, sizeof(digit));
}

void BigNum :: print()
{
    INT i;

    if(sign) printf("-");
    printf("%ld", digit[len - 1]);
    for(i = len - 2; i >= 0; --i)
    {
    switch(BASE)
	{
	case 10:
	    printf("%ld", digit[i]);
	    break;
	case 100:
	    printf("%02ld", digit[i]);
	    break;
	case 1000:
	    printf("%03ld", digit[i]);
	    break;
	case 10000:
	    printf("%04ld", digit[i]);
	    break;
	case 100000:
	    printf("%05ld", digit[i]);
	    break;
	case 1000000:
	    printf("%06ld", digit[i]);
	    break;
	case 10000000:
	    printf("%07ld", digit[i]);
	    break;
	case 100000000:
	    printf("%08ld", digit[i]);
	    break;
	case 1000000000:
	    printf("%09ld", digit[i]);
	    break;
	default:
	    break;
	}
    }
}


char X[MAXN], Z[120];
BigNum Table[2][MAXN];

int Equal() {
	int i;
	for(i = 1; X[i]; i++){
		if(X[i] != Z[i]) return 1;
	}
	return 0;
}

void Assaign(int x) {
	int i, p = 0, j;
	for(i = 0; i<2; i++)
		for(j = 0; j<= x; j++)
			Table[i][j] = p;
}

void Dynamic(int x, int z) {
	int i, j, ind1 = 0, ind2 = 1;
	Assaign(x);
	for(i = 1; i<= x; i++) {
		if(X[i] == Z[1]){
			Table[1][i].add(Table[1][i],Table[1][i-1]);
			Table[1][i].add(Table[1][i],1);
		}
		else Table[1][i] = Table[1][i-1];
	}
	for(i = 2; i<= z; i++) {
		for(j = 1; j <= x; j++) {
			if(Z[i] == X[j]) {
				Table[ind1][j] .add(Table[ind1][j-1],Table[ind2][j-1]);
			}
			else Table[ind1][j] = Table[ind1][j-1];
		}
		ind1 = !ind1;
		ind2 = !ind2;
	}
	Table[ind2][x].print();
	printf("\n");
}
void Cal() {
	int x, z;
	for(x = 1; X[x]; x++);
	for(z = 1; Z[z]; z++);
	x--;
	z--;
	if(x == z) {
		if(!Equal())
			printf("1\n");
		else printf("0\n");
		return;
	}
	if(x<z) {
		printf("0\n");
		return;
	}
	Dynamic(x,z);
}

int main() {
	int ks;
	char ss[20];
	//freopen("c:\\h.txt","r",stdin);
	gets(ss);
	sscanf(ss,"%d",&ks);
	while(ks--) {
		 gets(X+1);
		 gets(Z+1);
		 Cal();
	}
	return 0;

}