Distinct Subsequences, Problem 10069 UVa, A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence X = x1x2…xm, another sequence Z = z1z2…zk is a subsequence of X if there exists a strictly increasing sequence <i1, i2, …, ik> of indices of X such that for all j = 1, 2, ……

Main.java

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

/*
 * Main.java
 *  java program model for www.programming-challenges.com
 */

class Main implements Runnable {
	static String ReadLn(int maxLength) { 
		byte line[] = new byte[maxLength];
		int length = 0, input = -1;
		try {
			while (length < maxLength) {
				input = System.in.read();
				if ((input < 0) || (input == '\n')) { break; }
				line[length++] += input;
			}

			if ((input < 0) && (length == 0)) { return null; } //eof
			return new String(line, 0, length);
		} catch (IOException e) { return null; }
	}

	public static void main(String args[]) { new Main().run(); }
	public void run() { new myStuff().run(); }
}

class myStuff implements Runnable {
	public void run() {
		String input;
		StringTokenizer idata;

		int T;
		String X, Z;

		input = Main.ReadLn(255);
		idata = new StringTokenizer(input);
		T = Integer.parseInt(idata.nextToken());
		
		while (T-- > 0) {
			input = Main.ReadLn(100001);
			idata = new StringTokenizer(input);
			X = idata.nextToken();

			input = Main.ReadLn(101);
			idata = new StringTokenizer(input);
			Z = idata.nextToken();
			
			Solution.solve(X, Z);
		}
	}

	private static class Solution {
		private static final int MAXX = 100000, MAXZ = 100;

		//Note prefixs are 1 based, 0 index corresponds to empty prefix
		private static final BigInteger[] P = new BigInteger[MAXZ + 1];

		private static void initBigIntArray() {
			for (int i = 0; i < P.length; i++) { P[i] = BigInteger.ZERO; }
		}

		public static void solve(String X, String Z) {
			BigInteger C=BigInteger.ZERO;
			
			initBigIntArray();

			//Base case-empty prefix
			P[0] = BigInteger.ONE;
			for (int i = 0; i < X.length(); i++) {
				int pl = Z.lastIndexOf(X.charAt(i));
				
				if (pl < 0){ continue; }
				
				if (pl == Z.length() - 1
						&& P[pl].compareTo(BigInteger.ZERO) > 0) {
					C = C.add(P[pl]);
				}

				for (int j = pl; j >= 0; j--) {
					if (Z.charAt(j) == X.charAt(i)
							&& P[j].compareTo(BigInteger.ZERO) > 0) {
						P[j + 1] = P[j + 1].add(P[j]);
					}
				}
			}

			System.out.println(C);
		}
	}
}