终于弄出来了，不会做的都是难题，会做的都是水题啊，水啊。
这道题的大意是：从母串里找出有多少个子串为给出的字串，分两步思考：
一 是先把状态方程写出来，由题分析我们可以这样设状态：
f[i][j] = f[i][j-1];
if(b[i] == a[j]) f[i][j] += f[i-1][j-1];
这里解释一下：这里的f[i][j]表示字串前 i 个组成的字串，在前 j 个母串中出现的次数，例如：
母串：babgbag 状态中前 j 个字符组成的字串
字串：bag 状态中前 i 个字母组成的字串
为什么这样可以呢：因为前 i 个字串在前 j 个母串中出现的次数必然大于在前 j - 1个母串中出现的次数，因此f[i][j] >= f[i][j-1]，如果a[j] != b[i] 则 f[i][j] = f[i][j-1]
如果相等，还要在此基础上加上前 j - 1 时存在的 i - 1的字串出现的次数（因为这个次数要与现在相等的这个字符重新组合），由此if(b[i] == a[j]) f[i][j] += f[i-1][j-1];
二要考虑的是因为出现的次数太大（2e100），要用高精度运算与保存；
最后要注意一点：f[i][j][k]初始化时要注意先初始化第一次比较；
代码如下：
#include<stdio.h>
#include<string.h>
int n;
char f[105][10010][105];
char a[10010], b[105], tg[105];
void add(char* s1, char* s2)
{
char s3[105];
memset(s3,0,sizeof(s3));
int lens1 = strlen(s1);
int lens2 = strlen(s2);
int t;
if(lens1>lens2) t = lens1;
else t = lens2;
int c = 0;
for(int i = 0; i <= t; i ++)
{
if(s1[i] == 0) s1[i] = '0';
if(s2[i] == 0) s2[i] = '0';
s3[i] = s1[i] - '0'+ s2[i] + c ;
c = 0;
if(s3[i]>'9')
{
c = 1;
s3[i] = s3[i] - '9'-1 + '0';
}
}
for(int i = 0; i <= t; i ++)
s1[i] = s3[i];
if(s1[t] == '0') s1[t] = 0;
for(int i = t; i >= 0; i --)
if(s2[t] != '0' && s2[t] != 0) break;
else s2[t] = 0;
}
void solve()
{
int lena = strlen(a+1);
int lenb = strlen(b+1);
memset(tg,0,sizeof(tg));
for(int i = 1; i <= lena; i ++)
{
for(int j = 0; j < 100; j ++)
f[1][i][j] = f[1][i-1][j];
tg[0] = '1';
if(b[1] == a[i]) add(f[1][i],tg);//printf("i=%d f[][]=%s\n",i,f[1][i]);
}
for(int i = 2; i <= lenb; i ++)
for(int j = i; j <= lena; j ++)
{
for(int k = 0; k < 100; k ++)
f[i][j][k] = f[i][j-1][k];
if(a[j] == b[i]) add(f[i][j],f[i-1][j-1]);//printf("j=%d f[][]=%s\n",j,f[i][j]);
}
int i;
for( i = 100; i >= 0; i --)
if(f[lenb][lena][i] != '\0') break;
for(int j = i; j >= 0; j --)
printf("%c",f[lenb][lena][j]);
puts("");
}
void input()
{
while(scanf("%d",&n) == 1)
{
while(n --)
{
scanf("%s%s",a+1,b+1);
solve();
}
}
}
int main()
{
input();
return 0;
}