Longest Common Contiguous Substring Length in C

Question

So the following is the code I wrote up for the algorithm. I cannot find what is wrong with it. The test cases are supposed to yield 12, 4, and 3 respectively but instead yield 8, 1, and 2 respectively. Did I misunderstand the algorithm structure?

#include <stdio.h>

#define MAX_STRING_LENGTH 100

void clear_memo(int memo[][MAX_STRING_LENGTH]);


// Returns the larger of a and b
int max(int a, int b){
  return a ? a > b : b;
}

int lcs_length(char A[], char B[], int i, int j, int memo[][MAX_STRING_LENGTH]){
  if(i == 0 && j == 0){
    clear_memo(memo);
  }

  if (memo[i][j] > 0){
    return memo[i][j];
  }

  if (A[i] == '\0' || B[j] == '\0'){
    memo[i][j] = 0;
  } 
  else if(A[i] == B[j]){
    memo[i][j] = 1 + lcs_length(A, B, i+1, j+1, memo);
  } 
  else{
    memo[i][j] = max(lcs_length(A, B, i+1, j, memo), lcs_length(A, B, i, j+1, memo));
  }

  return memo[i][j];
}

// Makes all the entries zero in the memo array
void clear_memo(int memo[][MAX_STRING_LENGTH]){
   for(int i = 0; i < MAX_STRING_LENGTH; i++){
    for(int j = 0; j < MAX_STRING_LENGTH; j++){
      memo[i][j] = 0;
    }
  }
}

// Tests the lcs_length() function
int main(){
  int memo[MAX_STRING_LENGTH][MAX_STRING_LENGTH];

  char a[] = "yo dawg how you doing?";
  char b[] = "yo dawg zhzzzozw?";
  printf("%d\n", lcs_length(a,b,0,0,memo));

  char c[] = "nano";
  char d[] = "nematode knowledge";
  printf("%d\n", lcs_length(c,d,0,0,memo));

  char e[] = "abcd";
  char f[] = "abdc";
  printf("%d\n", lcs_length(e,f,0,0,memo));

  return 0;
}

Answer 1

Your max is wrong. a? a>b:b; means if a is non zero, return a>b( which returns 1 if a>b and 0 otherwise) and if a is zero, returns b. So a is never returned even if it is greater and b is returned only if a is 0 irrespective of which is greater. Use

int max(int a, int b){

    return a>b?a:b;
}