2013年8月21日

LCS among 3 strings

int lcs(char * a, char * b, char * c) {
  int len[20][20][20], ans = 0;
  for (int i = 1; a[i]; i++) {
    for (int j = 1; b[j]; j++) {
      for (int k = 1; c[k]; k++) {
        if (a[i] == b[j] && b[j] == c[k]) {
          len[i][j][k] = len[i - 1][j - 1][k - 1] + 1;
          ans = max(ans, len[i][j][k]);
        } else {
          len[i][j][k] = max(len[i - 1][j][k], max(len[i][j - 1][k], len[i][j][k - 1]));
        }
      }
    }
  }
  return ans;
}

沒有留言:

張貼留言