UVA 10069 Distinct Subsequences

//  [解题方法]
//  dp[i][j]表示Z串的[0~i]子串在X串的[0~(j-1)]子串中的出现次数
//  初始化：dp[i][0] = 0
//  状态转移1：
//  dp[0][j+1] = (Z[0]==X[j])?(dp[0][j]+1):(dp[0][j])
//  状态转移2(i>0)：
//  dp[i][j+1] = (Z[i]==X[j])?(dp[i][j]+dp[i-1][j]):(dp[i][j])
//  这题需要大数运算，我偷懒用了java
//  另外由于每次转移实际上只用到两个数组，所以这里就只开了两个数组循环使用，相当于滚动数组了

import java.util.*;
import java.io.*;
import java.math.*;

public class Main
{
	static public void main (String[] args) throws IOException
	{
		Scanner cin = new Scanner (new BufferedInputStream (System.in));
		BigInteger dp[][] = new BigInteger [2][10001];
		int t, n, m, i, j, k;
		String s, p;
		t = cin.nextInt();
		while (t > 0)
		{
			t--;
			s = cin.next();
			p = cin.next();
			n = s.length();
			m = p.length();
			k = 0;
			dp[0][0] = dp[1][0] = BigInteger.valueOf(0);
			for (j = 0; j < n; j++)
			{
				dp[k][j+1] = dp[k][j];
				if (s.charAt(j) == p.charAt(0))
					dp[k][j+1] = dp[k][j+1].add(BigInteger.valueOf(1));
			}
			for (i = 1; i < m; i++)
			{
				k = (k+1)%2;
				for (j = 0; j < n; j++)
				{
					dp[k][j+1] = dp[k][j];
					if (s.charAt(j) == p.charAt(i))
						dp[k][j+1] = dp[k][j+1].add(dp[(k+1)%2][j]);
				}
			}
			System.out.println(dp[k][n]);
		}
	}
}