SW 3304 최장공통부분수열 [D3]

/*

최장 공통 부분 수열

*/

#include <stdio.h>

#include <string>

#include <iostream>

#define MAX 1001

using namespace std;

int T;

int arr[MAX][MAX] = { 0, };

char str1[1001], str2[1001];

void init()

{

for (int i = 0; i < MAX; i++)

for (int j = 0; j < MAX; j++)

arr[i][j] = 0;

}

int lcs(){

int i, j;

for (i = 1; str1[i-1] != '\0'; i++){

for (j = 1; str2[j - 1] != '\0'; j++){

if (str1[i-1] == str2[j-1])

arr[i][j] = arr[i - 1][j - 1] + 1;

else

arr[i][j] = arr[i][j - 1] > arr[i - 1][j] ? arr[i][j - 1] : arr[i - 1][j];

}

}

return arr[i-1][j-1];

}

int main()

{

int ans;

scanf("%d", &T);

for (int tc = 1; tc <= T; tc++){

cin >> str1 >> str2;

//cout << str1 << str2 << endl;

init();

ans = lcs();

printf("#%d %d\n", tc, ans);

}

return 0;

}