1264. [S/W 문제해결 응용] 8일차 - 이미지 유사도 검사

LCS =>최장공통부분문자열을 구하는 문제 

참고 블로그 https://www.crocus.co.kr/787

LCS(Longest Common Subsequence) 알고리즘

두 문자열의 공통 문자 개수를 테이블로 표현하는데 첫 인덱스 위치는 0으로 세팅하는 것이 관례

일치 하는 경우 대각선의 +1이 들어가므로, 

만약 두 문자가 일치하게 된다면 첫번째 두번째 문자열의 비교기준 두 문자열의 전단계 일치 개수에서 +1이 되는 것이므로 대각선에서 +1이고,

일치하지 않다면 왼쪽 혹은 위쪽 개수에서 최대값의 개수를 유지하게 된다.

 

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int N;
string str1, str2;
int arr[501][501];


int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		
		cin >> N >> str1 >> str2;
		memset(arr, 0, sizeof(arr));


		string temp = '0' + str1;
		string temp2 = '0' + str2;

		for (int i = 0; i < temp.size(); i++)
		{
			for (int j = 0; j < temp2.size(); j++)
			{
				if (!i || !j)
				{
					arr[i][j] = 0;
				}
				else
				{
					if (temp[i] == temp2[j])
					{
						arr[i][j] = arr[i - 1][j - 1] + 1;
					}
					else
					{
						if (arr[i - 1][j] < arr[i][j - 1])
						{
							arr[i][j] = arr[i][j - 1];
						}
						else {
							arr[i][j] = arr[i - 1][j];
						}
					}

				}
				
			}
		}
		printf("#%d %.2f\n",test_case,(double)arr[temp.size() - 1][temp2.size() - 1]/(double)N *(double)100);
		
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}