A응실 이미지 유사도 검사 / LCS 디피

1. FS, SS 받고 2. LCS 를 디피로 검사해서 3. 제일 긴 것을 찾으면 됨

#include <stdio.h> #define MAX(a, b) ((a) > (b) ? (a) : (b)) //#define FS_SS_LEN 502 //#define LCS_LEN 501 #define FS_SS_LEN 15 #define LCS_LEN 15 char FS[FS_SS_LEN]; char SS[FS_SS_LEN]; int LCS[LCS_LEN][LCS_LEN]; int main() { freopen("input.txt", "r", stdin); int i, j, N, T, tc; double ans; scanf("%d", &T); for (tc = 1; tc <= T; tc++) { scanf("%d", &N); scanf(" %s", FS + 1); scanf(" %s", SS + 1); for (i = 1; i <= N; i++) { for (j = 1; j <= N; j++) { if (FS[i] == SS[j]) { LCS[i][j] = LCS[i - 1][j - 1] + 1; } else { LCS[i][j] = MAX(LCS[i - 1][j], LCS[i][j - 1]); } } } ans = ((double)LCS[N][N] / N) * 100; printf("#%d %lf\n", tc, ans); } return 0; }