CodeChef submission 131038 (JAVA) plaintext list. Status: TLE, problem J2, contest NOV09. By vector9x (vector9x), 2009-11-11 14:42:22.
import java.io.*;
import java.util.*;
import java.awt.Point;
 
public class Main {
	static BufferedReader input;
	
	public static void main(String[] args) throws IOException 
	{
		Locale.setDefault(Locale.US);
		input=new BufferedReader(new InputStreamReader(System.in));
		//input=new BufferedReader(new FileReader("input.txt"));
		int numCasos = Integer.parseInt(input.readLine());
		
		for(int caso=0; caso<numCasos; caso++)
		{
			//long ini = System.currentTimeMillis();
			A=input.readLine();
			B=input.readLine();
			input.readLine();
			/*
			String corta, larga;
			if(A.length()<B.length()) {
				corta = A;
				larga = B;
			}
			else {
				corta = B;
				larga = A;
			}
			
			if(larga.startsWith(corta) || larga.endsWith(corta)) {
				System.out.println(corta.length()+" 1");
				continue;
			} 
			*/
			solve();
			
			//System.err.println("time "+(System.currentTimeMillis()-ini)/1000.0);
		}
	}
	
	static String A, B;
	static short[][] lcs=new short[1001][1001]; 
	static boolean[][] pivot=new boolean[1001][1001];
	//static byte[][] prev=new byte[1001][1001];
	static final int MOD = 23102009;
	static final byte IZQ='<', ARR='^', DIAG='\\', AMBOS='+';
	
	
	static PairSet[][] from=new PairSet[1001][1001];
	
	static {
		from[0][0]=new PairSet();
		for(int i=1;i<1001;i++){
			from[i][0]=from[0][0];
			from[0][i]=from[0][0];
		}
	}
	
	static char A_(int idx) {
		return A.charAt(idx-1);
	}
	
	static char B_(int idx) {
		return B.charAt(idx-1);
	}
	
	static void solve()
	{
		for(int i=1; i<=A.length(); i++) {
			for(int j=1; j<=B.length(); j++) {
				if(A_(i)==B_(j)) {
					lcs[i][j] = (short)(lcs[i-1][j-1] + 1);
					pivot[i][j]=true;
					//prev[i][j]=DIAG;
					if(pivot[i-1][j-1]) {
						from[i][j]=new PairSet();
						from[i][j].add(new Point(i-1,j-1));
					}
					else {
						from[i][j]=from[i-1][j-1];
					}
				}
				else {
					if(lcs[i-1][j]>lcs[i][j-1]) {
						lcs[i][j] = lcs[i-1][j];
						//prev[i][j] = ARR;
						if(pivot[i-1][j]) {
							from[i][j]=new PairSet();
							from[i][j].add(new Point(i-1,j));
						} else {
							from[i][j]=from[i-1][j];
						}
					}
					else if(lcs[i][j-1]>lcs[i-1][j]) {
						lcs[i][j] = lcs[i][j-1];
						//prev[i][j] =  IZQ;
						if(pivot[i][j-1]) {
							from[i][j]=new PairSet();
							from[i][j].add(new Point(i,j-1));
						} else {
							from[i][j]=from[i][j-1];
						}
					}
					else {
						lcs[i][j] = lcs[i-1][j];
						//prev[i][j] = AMBOS;
						from[i][j]=new PairSet();
						from[i][j].addAll(from[i-1][j]);
						from[i][j].addAll(from[i][j-1]);
					}
					pivot[i][j] = false;
				}
			}
		}
		
		//printLCS();
		
		for(int i=1;i<=A.length(); i++)	{
			Arrays.fill(memo[i],1,B.length()+1, -1);
			//Arrays.fill(memoAnts[i],1,B.length()+1, null);
		}
		
		
		int total=0;
 
		total = go(A.length(), B.length());
		System.out.println(lcs[A.length()][B.length()]+" "+total);
	}
 
	static int[][] memo=new int[1002][1002];
	
	static int go(int ipiv, int jpiv /*, int deep*/)
	{
		//print(deep,"go("+ipiv+","+jpiv+") "+(char)prev[ipiv][jpiv]);
		
		if(memo[ipiv][jpiv]!=-1) {
			//print(deep, "memo! "+ipiv+","+jpiv);
			return memo[ipiv][jpiv];
		}
		
		if(pivot[ipiv][jpiv] && lcs[ipiv][jpiv]==1) {
			return memo[ipiv][jpiv]=1;
		}
		
		int res = 0;
		Arrays.fill(usadoFila, 1, ipiv+1, false);
		Arrays.fill(usadoCol, 1, jpiv+1, false);
		
		for(Point piv: from[ipiv][jpiv]) {
			//print(deep,"["+piv.x+","+piv.y+"]");
			if(!usadoFila[piv.x] && !usadoCol[piv.y]) {
				res += go(piv.x,piv.y);
				res %= MOD;
				usadoFila[piv.x]=true;
				usadoCol[piv.y]=true;
			}
		}
		
		return memo[ipiv][jpiv]=res;
	}
	
	
	static int __go(int ipiv, int jpiv /*, int deep*/)
	{
		//print(deep,"go("+ipiv+","+jpiv+") "+(char)prev[ipiv][jpiv]);
		
		if(memo[ipiv][jpiv]!=-1) {
			//print(deep, "memo! "+ipiv+","+jpiv);
			return memo[ipiv][jpiv];
		}
		
		if(pivot[ipiv][jpiv] && lcs[ipiv][jpiv]==1) {
			return memo[ipiv][jpiv]=1;
		}
		
		int res = 0;
		for(Point piv: pivsAnteriores(ipiv, jpiv)) {
			//print(deep,"["+piv.x+","+piv.y+"]");
			res += go(piv.x,piv.y);
			res %= MOD;
		}
		
		return memo[ipiv][jpiv]=res;
	}
	
	
	static boolean[][] visited=new boolean[1001][1001];
	static boolean[] usadoFila=new boolean[1001];
	static boolean[] usadoCol=new boolean[1001];
	//static PairSet[][] memoAnts=new PairSet[1001][1001];
	static PairSet pivsAnteriores(int i, int j) {
		//if(memoAnts[i][j]!=null) return memoAnts[i][j];
		//System.out.println("pivsAnteriores("+i+","+j);
		for(int k=0; k<=i; k++)
			Arrays.fill(visited[k],0,j+1, false);
		
		Arrays.fill(usadoFila, 1, i+1, false);
		Arrays.fill(usadoCol, 1, j+1, false);
		
		PairSet res = new PairSet();
		pivsAnterioresIter(res,i,j, true);
		//memoAnts[i][j]=res;
		return res;
	}
	
	static void pivsAnterioresIter(PairSet set, int i, int j, boolean first)
	{
		int mov;
		outer:
		for(;;) {
			if(visited[i][j]) return;
			visited[i][j]=true;
			//print(deep,"<"+i+","+j+">");
			
			if(!first && pivot[i][j]) {
				if(!usadoFila[i] && !usadoCol[j]) {
					set.add(new Point(i,j));
					//print(deep,"agregando "+i+","+j);
					usadoFila[i]=true;
					usadoCol[j]=true;
				}
				return;
			}
			first=false;
			mov=0;
			
			switch(mov) 
			{
			case IZQ: j--; break;
			case ARR: i--; break;
			case DIAG: i--; j--; break;
			case AMBOS:
				pivsAnterioresIter(set,i-1,j,false);
				pivsAnterioresIter(set,i,j-1,false);
				break outer;
			default: 
				//System.out.println(".");
				break outer;
				
			}
		}
		//System.out.println("))"
	}
	
	
	static void print(int deep, String str)
	{
		for(int i=0;i<deep;i++) System.err.print(" ");
		System.err.println(str);
	}
 
	static void printLCS()
	{
		for(int i=1; i<=A.length(); i++) {
			for(int j=1; j<=B.length(); j++) {
				if(pivot[i][j])
					System.err.print("["+lcs[i][j]+"]");
				else
					System.err.print(" "+lcs[i][j]+" ");
			}
			System.err.println();
		}
	}
	
	static class PairSet extends HashSet<Point>{}
}