Longest Common Subsequence

Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:

abcdgh

aedfhr

is adh of length 3.

Input consists of pairs of lines. The first line of a pair contains the first string and the second line contains the second string. Each string is on a separate line and consists of at most 1,000 characters. 

For each subsequent pair of input lines, output a line containing one integer number which satisfies the criteria stated above.

 

Sample input

a1b2c3d4e

zz1yy2xx3ww4vv

abcdgh

aedfhr

abcdefghijklmnopqrstuvwxyz

a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0

abcdefghijklmnzyxwvutsrqpo

opqrstuvwxyzabcdefghijklmn

 

Output for the sample input

4

3

26

14

#include "stdafx.h"

#include "string.h"

 

int _tmain(int argc, _TCHAR* argv[])

{

      int lena,lenb,i,j,k,ind,maxlen,templen,found;

      char A[100],B[100];

      while(scanf("%s",A))

      {

            maxlen=0;templen=0;found=0;

            scanf("%s",B);

            lena=strlen(A);

            lenb=strlen(B);

            for(i=0;i<lena;i++)

            {

                  ind=-1;j=i;templen=0;

                  while(j<lena)

                  {

                        found=0;

                        for(k=ind+1;k<lenb;k++)

                        {

                              if(A[j]==B[k] && j<lena)

                              {

                                    templen++;

                                    ind=k;

                                    j++;

                                    found=1;

                                    break;

                              }

                        }

                        if(found!=1)

                        {

                              j++;

                        }

                  }

                  if(maxlen<templen)

                  {

                        maxlen=templen;

                  }

            }

            printf("%d\n",maxlen);

      }

      return 0;

}