CodeChef submission 130630 (C) plaintext list. Status: WA, problem J2, contest NOV09. By rookie (rookie), 2009-11-11 10:52:14.
#include<stdio.h>
#include<string.h>
 
int L[1000][1000];
int L1[1000][1000];
int D[1000][1000];
 
int lcs_fun(char[],char[],int,int);
 
int main()
{
	char s[1002],t[1002];
	int tc,index=0,m,n,i=0,j=0,l1=0,l2=0,x=0;
 
	scanf("%d",&tc);
	while(index<tc)
	{
		scanf("%s",s);
		scanf("%s",t);
		m=strlen(s);n=strlen(t);
		
	/*	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
		{
			if(i==0 || j==0)
			L1[i][j]=0;
		
			else if(i>0 && j>0 && s[i]==t[j])	
			{
				L1[i][j]=L1[i-1][j-1]+1;
			}
			else
			{
				l1=L1[i-1][j];
				l2=L1[i][j-1];
		        	L1[i][j]=(l1>l2)?l1:l2;
			}	
			//printf("%d ",l1);
		}
			if(L[m-1][n-1]==0)
			printf("%d ",(L1[m-1][n-1]));
			else
			printf("%d ",(1+L1[m-1][n-1]));
	*/
		
	/*	for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
			{
				if(i==0 || j==0)
				L1[i][j]=0;
				else
				L1[i][j]=-1;
			}
		}
	*/
			  
		//printf("%d ",lcs_fun(s,t,m-1,n-1));	
		//x=lcs_fun(s,t,m-1,n-1);
		//if(x==0) printf("%d ",x);
		//else
		//printf("%d ",1+x);
 
		for(j=0;j<n;j++)
		for(i=0;i<m;i++)
		{
			if(i==0 || j==0)
			{
				L[i][j]=0;
				D[i][j]=1;
			}
			else
			{
				D[i][j]=0;
	
				if(s[i]==t[j])
				{
					L[i][j]=L[i-1][j-1]+1;
					D[i][j]=D[i-1][j-1];
				}
				else
				{
					l1=L[i-1][j];
					l2=L[i][j-1];
 
					L[i][j]=(l1>l2)?l1:l2;
 
					if(L[i-1][j]==L[i][j])
					D[i][j]=D[i][j]+D[i-1][j];
					if(L[i][j-1]==L[i][j])
					D[i][j]=D[i][j]+D[i][j-1];
					if(L[i-1][j-1]==L[i][j])
					D[i][j]=D[i][j]-D[i-1][j-1];
				}
			}
			
  		}
		//printf("i=%d,i=%d,%d ",i,j,D[i-1][j-1]);
		printf("%d ",1+L[m-1][n-1]);
		printf("%d ",(D[m-1][n-1])%23102009);
		printf("\n");
		
		/*for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
			printf("%d ",L1[i][j]);
			printf("\n");
		}*/
	
		index++;
	}
	
	return 0;
}
 
int lcs_fun(char x[],char y[],int i,int j)
{
	int l1,l2;
	
	if(L1[i][j]!=-1)
	return L1[i][j];	
 
	if(x[i]==y[j])
	{
		L1[i][j]= (lcs_fun(x,y,i-1,j-1)+1);
	}
	else
	{
		l1=lcs_fun(x,y,i-1,j-1);
		l2=lcs_fun(x,y,i,j-1);
	
		l1=((l1>l2)?l1:l2);
		L1[i][j]=l1;
		 
	//return (L1[i][j]);
	
	}
	return (L1[i][j]);
}