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