Patch for /trunk/src/lang-proto.js

template<class T> T MAX( T a, T b ){ return a>b ? a:b; }

char A[1005], B[1005];
int la, lb; /* length of A and B */
int memo[1005][1005]; /* memoize for dp */

int LCS(int i, int j) {
  if(i==la || j==lb) return 0; /* equals to string(s) */

  if(memo[i][j] != -1) return memo[i][j];  /* obvioulsy memo is traversed by 
this i and j */

  if(A[i]==B[j]) memo[i][j] = 1 + LCS(i+1, j+1); /* new call by i,j both 
increased 1 A[i] and A[j] same */

  else {   /* A[i] and A[j] are not same */
   int a = LCS(i, j+1);  /* one call by increasing j */
   int b = LCS(i+1, j);  /* another by increasing i */
    memo[i][j] = MAX(a, b);  /* maximum of a and b is pushed in memo */
  }
  return memo[i][j];
}

int main( ){
  //freopen( "in.txt", "r", stdin );
  //freopen( "out.txt", "w+", stdout );

  for(i=0; i<1005; i++) A[i] = B[i] = '\0';  /* clearing */

  while( gets(A) ){
    gets(B);
    la = strlen(A);
    lb = strlen(B);
    memset(memo, -1, sizeof(memo));
    res = LCS(0,0);  /* call starts here */
    printf("%d\n", res);
  }
  return 0;
}

Original issue reported on code.google.com by Mail.pr...@gmail.com on 8 Jul 2012 at 11:47

Attachments:

lang-proto.js.patch

h13i32maru / google-code-prettify

Patch for /trunk/src/lang-proto.js #228