做题感悟：这题和最长公共子序列差不多，开始没注意到数据范围，交上果断wa！！
解题思路： DP+大数 ，用 dp [ i ] [ j ] 代表子串 j 在子串中出现的次数。
动态方程：
s1[ i ] == s2[ j ] --> dp [ i ] [ j ] = dp [ i-1 ] [ j - 1 ] + dp [ i ] [ j -1 ] ; 即：字串 j -1 在 i 中出现的次数（应为s1[ i ] == s2[ j ] 所以相当于串 j ） + 串 j 在 串 i -1 中出现的次数。
s1[ i ] ！= s2[ j ]--> dp[ i ][ j ] = dp [ i ] [ j - 1 ] ; 即： 串 j 在 串 i -1 中出现的次数（因为s1[ i ] ！= s2[ j ]）
代码：
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const int MX = 10000 + 10 ;
int a[MX][110],b[MX][110] ;
char s1[MX],s2[MX] ;
void search(int j,int(*a)[110],int(*b)[110])
{
int c=0 ;
for(int i=0 ;i<100 ;i++)
if(a[j][i]+b[j][i]+c>9)
b[j+1][i]=a[j][i]+b[j][i]+c-10 , c=1 ;
else
b[j+1][i]=a[j][i]+b[j][i]+c , c=0 ;
}
void work(int j,int (*a)[110])
{
for(int i=0 ;i<100 ;i++)
a[j+1][i]=a[j][i] ;
}
void print(int x,int (*p)[110])
{
int i,j ;
for(i=100 ;i>=0 ;i--)
if(p[x][i])
break ;
if(i==-1) cout<<"0" ;
for(j=i ;j>=0 ;j--)
cout<<p[x][j] ;
cout<<endl ;
}
int main()
{
int Tx ;
scanf("%d",&Tx) ;
while(Tx--)
{
scanf("%s%s",s1+1,s2+1) ;
memset(a,0,sizeof(a)) ;
memset(b,0,sizeof(b)) ;
int len1=strlen(s1+1) ;
int len2=strlen(s2+1) ;
for(int i=0 ;i<=10000 ;i++)
a[i][0]=1 ;
for(int i=1 ;i<=len2 ;i++)
{
for(int j=1 ;j<=len1 ;j++)
if(s2[i]==s1[j])
i%2 ? search(j-1,a,b) : search(j-1,b,a) ;
else
i%2 ? work(j-1,b) : work(j-1,a) ;
i%2 ? memset(a,0,sizeof(a)) : memset(b,0,sizeof(b)) ;
}
len2%2 ? print(len1,b) : print(len1,a) ;
}
return 0 ;
}