C :

#include "stdio.h"
#include "string.h"
#define N 5005
#define M 100000000
int n,m;
char a[N],b[N];
int f[2][N],g[2][N];
int max(int a,int b){if(a>b)return a;return b;}
int main()
{
	int i,j,k;
	scanf("%s%s",a,b);
	n=strlen(a)-1;
	m=strlen(b)-1;
	for(i=0;i<=m;i++)g[0][i]=1;g[1][0]=1;
	for(i=1;i<=n;i++)
	{
		k=i&1;
		for(j=1;j<=m;j++)
		{
			if(a[i-1]==b[j-1])f[k][j]=f[!k][j-1]+1,g[k][j]=g[!k][j-1];
			else f[k][j]=max(f[!k][j],f[k][j-1]),g[k][j]=0;
			if(f[k][j]==f[!k][j])g[k][j]+=g[!k][j];
			if(f[k][j]==f[k][j-1])g[k][j]+=g[k][j-1];
			if(f[k][j]==f[!k][j-1])g[k][j]-=g[!k][j-1];
			g[k][j]=(g[k][j]+M)%M;
		}
	}
	printf("%d\n%d\n",f[k][m],g[k][m]);
	return 0;
}

C++ :

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int m=(int)1E8;
string s1,s2;
int f[2][5001]={0},g[2][5001]={0};
void init();
void work();
int my_max(int,int);
int main()
{
	//freopen("lcs5.in","r",stdin);
	//freopen("a.txt","w",stdout);
	init();
	work();
	return 0;
}
void init()
{
	cin>>s1;
	cin>>s2;
}
void work()
{
	int len1=s1.size()-1,len2=s2.size()-1;
	//cout<<len1<<' '<<len2<<endl;
	for(int i=0;i<=len2;i++)g[0][i]=1;
	//f[0][0]=1;
	int k;
	for(int i=1;i<=len1;i++)
	{
		k=i & 1;
		memset(g[k],0,sizeof(g[k]));
		memset(f[k],0,sizeof(f[k]));
		g[k][0]=1;
		g[!k][0]=1;
		for(int j=1;j<=len2;j++)
		{
			if(s1[i-1]==s2[j-1])
			{
				f[k][j]=f[!k][j-1]+1;
				g[k][j]=g[!k][j-1];
				g[k][j]%=m;
				if(f[k][j]==f[!k][j])
				{
					g[k][j]+=g[!k][j];
					g[k][j]%=m;
				}
				if(f[k][j-1]==f[k][j])
				{
					g[k][j]+=g[k][j-1];
					g[k][j]%=m;
				}
			}
			else
			{
				if(f[!k][j]>f[k][j-1])
				{
					f[k][j]=f[!k][j];
					g[k][j]+=g[!k][j];
					g[k][j]%=m;
				}
				if(f[!k][j]<f[k][j-1])
				{
					f[k][j]=f[k][j-1];
					g[k][j]+=g[k][j-1];
					g[k][j]%=m;
				}
				if(f[!k][j]==f[k][j-1])
				{
					f[k][j]=f[!k][j];
					g[k][j]+=g[!k][j]+g[k][j-1];
					if(f[!k][j-1]==f[k][j])g[k][j]-=g[!k][j-1];
					g[k][j]=(g[k][j]+3*m)%m;
				}
			}
			//cout<<j<<' '<<g[k][j]<<endl;
		}
	}
	cout<<f[k][len2]<<endl;
	cout<<g[k][len2]<<endl;
}
int my_max(int x,int y)
{
	if(x>y)return x;
	else return y;
}

Pascal :

const aa=100000000;
var
  f,g:array[0..1,0..5005] of longint;
  st,stt:array[0..5005] of char;
  n,m,i,j,x,y:longint;

function max(x,y:longint):longint;
begin
  if x<=y then exit(y);
  exit(x);
end;


procedure init;
var i,j:longint;
begin
   n:=0;
   st[n]:='a';
   while st[n]<>'.' do
    begin
      inc(n);
      read(st[n]);
    end;
    readln;
   dec(n);
   m:=0;
   stt[m]:='b';
   while stt[m]<>'.' do
   begin
      inc(m);
      read(stt[m]);
   end;
   dec(m);
end;

begin
        init;
	fillchar(f,sizeof(f),0);
	filldword(g[0],sizeof(g[0])>>2,1);
	for i:=1 to n do
	  begin
	         x:=i and 1;
		 y:=x xor 1;
		 fillchar(g[x],sizeof(g[x]),0);
		 fillchar(f[x],sizeof(f[x]),0);
		 g[x,0]:=1;
		 for j:=1 to m do
		 begin
		 f[x,j]:=max(f[x,j-1],f[y,j]);
		     if st[i]=stt[j] then
			   begin
			     f[x,j]:=max(f[x,j],f[y,j-1]+1);
			     g[x,j]:=g[y,j-1];
				 if f[x,j]=f[y,j] then g[x,j]:=g[x,j]+g[y,j];
				 if f[x,j]=f[x,j-1] then g[x,j]:=g[x,j]+g[x,j-1];
				 if g[x,j]>=aa then g[x,j]:=g[x,j] mod aa;
                                 if g[x,j]<0 then g[x,j]:=g[x,j]+aa;
			   end else
			   begin
				 if f[x,j]=f[y,j] then g[x,j]:=g[x,j]+g[y,j];
				 if f[x,j]=f[x,j-1] then g[x,j]:=g[x,j]+g[x,j-1];
                                 if f[x,j]=f[y,j-1] then g[x,j]:=g[x,j]-g[y,j-1];
                                 if g[x,j]>=aa then g[x,j]:=g[x,j] mod aa;
                                 if g[x,j]<0 then g[x,j]:=g[x,j]+aa; 
                           end;
		end;
	  end;
	writeln(f[n and 1,m]);
	writeln(g[n and 1,m]);
end.