UVa 10405 - Longest Common Subsequence

Accepted date: 2011-11-11
Ranking (as of 2013-07-13): 159 out of 6767
Language: C++

/*
  UVa 10405 - Longest Common Subsequence

  To build using Visual Studio 2008:
    cl -EHsc -O2 longest_common_subsequence.cpp
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int nr_chars_max = 1024;
char first_s[nr_chars_max], second_s[nr_chars_max];
int lcs_c[2][nr_chars_max];

int lcs(int first_s_length, int second_s_length)
{
  memset(lcs_c[0], 0, sizeof(int) * (second_s_length + 1));
  memset(lcs_c[1], 0, sizeof(int) * (second_s_length + 1));
  for (int i = 1; i <= first_s_length; i++) {
    int ci = i % 2, pi = (i - 1) % 2;
    for (int j = 1; j <= second_s_length; j++) {
      if (first_s[i - 1] == second_s[j - 1])
        lcs_c[ci][j] = lcs_c[pi][j - 1] + 1;
      else
        lcs_c[ci][j] = max(lcs_c[ci][j - 1], lcs_c[pi][j]);
    }
  }
  return lcs_c[first_s_length % 2][second_s_length];
}

int main()
{
  while (gets(first_s)) {
    gets(second_s);
    printf("%d\n", lcs(strlen(first_s), strlen(second_s)));
  }
  return 0;
}