#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>

//Run By LCS.
// O (m*n)
// DP implementation
const char* GetSameString (char const* ArgA,char const* ArgB, int *pN){
 int nA = strlen(ArgA);
 int nB = strlen(ArgB);
 if (!nA || !nB) return 0;
 
 int* CompareArr=new int[nB];
 int max=0,maxJ=0;
 for(int iloop=0;iloop<nA;iloop++){
      for(int jloop=nB-1;jloop>=0;jloop--){
           CompareArr[jloop]=(ArgB[jloop]==ArgA[iloop])?( (iloop==0||jloop==0)?1:CompareArr[jloop-1]+1):0;
           if(CompareArr[jloop]>=max)
           {
                max=CompareArr[jloop];
                maxJ=jloop;
           }
      }
 }
 delete []CompareArr;
 if(max>0)
 {
  *pN = max;
  return ArgB+maxJ-max+1;
 }
 else
    return 0;
}


void main()
{
    printf("LCS algorithm to get the longest common substring of 2 strings.\n");
    printf("input string 1:\n");
    char s1[500];
    scanf("%s", s1);
    printf("input string 2:\n");
    char s2[500];
    scanf("%s", s2);
    int N;
    const char *p = GetSameString(s1, s2, &N);
    if(p)
    {
        printf("s2 pos:%d, length %d\n", p-s2, N);
        for(const char *pp=p; pp<p+N; pp++)
            putchar(*pp);
        printf("\n");
    }
    else
        printf("No common\n");
}