Algorithms/Dynamic Programming/Longest Common Subsequence

Last-modified: 2008-05-23 (金) 11:00:22

Longest Common Subsequence

最長共通部分列

Program

int data[MAX][MAX], mm;

void lcs() {
  for(int i = 1 ; i <= a.size() ; i++) {
    for(int j = 1 ; j <= b.size() ; j++) {
      if (a[i - 1] == b[j - 1]) {
        data[i][j] = data[i - 1][j - 1] + 1;
      } else {
        if(data[i - 1][j] < data[i][j - 1]) {
          data[i][j] = data[i][j - 1];
        } else {
          data[i][j] = data[i - 1][j];
        }
      }
    }
  }

  mm = 0;

  for(int i = 0 ; i <= a.size() ; i++) {
    for(int j = 0 ; j <= b.size() ; j++) {
      if(data[i][j] > mm) {
        mm = data[i][j];
      }
    }
  }

  cout << mm << endl;
}