//Najdluzsze wspolne podslowo
//www.algorytm.org
//(c)2007 Tomasz Lubinski


public class Podtekst {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
        String s1,s2;
        int m,n,maxi,ind;
        int a[][];

        System.out.println("Podaj pierwszy ciag");
        s1 = Console.readString();
        System.out.println("Podaj drugi ciag");
        s2 = Console.readString();

        m = s1.length();
        n = s2.length();
        maxi = 0;
        ind = 0;
        a = new int[Math.max(m,n)+1][Math.max(m,n)+1];
        for(int i=0;i<Math.max(m,n)+1;i++)
        {
                a[0][i]=0;
                a[i][0]=0;
        }
        for(int i=1;i<=m;i++)
                for(int j=1;j<=n;j++)
                        if(s1.charAt(i-1)!=s2.charAt(j-1)) 
                        	a[i][j]=0;
                        else
                        {
                                a[i][j]=a[i-1][j-1]+1;
                                if(a[i][j]>maxi)
                                {
                                       maxi=a[i][j];
                                       ind=i;
                                }
                        }

        System.out.println("Najdluzszy wspolny podciag ma dlugosc " + maxi);
        if (maxi!=0)
        {
                System.out.print("Jest to: " + s1.substring(ind-maxi, ind));
        }
	}

}