c - C中最长的公共(public)连续子串长度

下面是我为算法编写的代码。我找不到它有什么毛病。测试用例应该分别产生12、4和3，而不是分别产生8、1和2。我是否误解了算法结构？

#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;
}

最佳答案

你的最大值错了。一个？a>b:b；
意思是如果a不为零，则返回a>b（如果a>b则返回1，否则返回0），如果a为零，则返回b。因此，即使a大于b，也不会返回a，而b仅在a为0时返回，而不管a大于b。
使用

int max(int a, int b){

    return a>b?a:b;
}

关于c - C中最长的公共(public)连续子串长度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23952857/