Find Longest Common Substring

Write a Logic/Pseudo Code to find longest common substring from two given strings. i.e. Out of two strings, “I like New York City the most.” And “Who else like New York City as I do?”, “like New York City” is the longest common substring.

Interview Candidate
Feb 7th, 2017
3
5548

Answer

Showing Answers 1 - 3 of 3 Answers

perumal

May 24th, 2017

Code is attached

Code
#include<stdio.h>


#include<string.h>


main()


{


char str1[100] = "I like New York City the most";


char str2[200] = "Who else like New York City as I do";


int matchstart=0;


int maxmatch=0;


int prevmatch=0;


int prevstart=0;


int i,j=0,k;


for (k=0;k<strlen(str1);k++)


{


j=k;


for (i=0;i<strlen(str2);i++)


{


        if (str1[j] == str2[i])


        {


//              printf("  %d",maxmatch);


          maxmatch++;


          if (0 == matchstart)


          {


             matchstart=i;


          }


          j++;


 


          if (j== strlen(str1))


          {


           break;


          }


        }


        else


        {


          if (prevmatch < maxmatch)


         {


          prevmatch = maxmatch;


          prevstart = matchstart;


         }


          maxmatch =0;


          matchstart =0;


          j=k;


 


        }


}


}


//printf("


 


 pre%d max%d",prevmatch,maxmatch);


if (prevmatch > maxmatch)


{


  for (i=prevstart;i<prevmatch+prevstart;i++)


  {


    printf("%c",str2[i]);


  }


}


else if(maxmatch)


{


  for (i=matchstart;i<maxmatch;i++)


  {


    printf("%c",str2[i]);


  }


}


 


}


~