#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/*
동적 프로그래밍으로 두 문자열의 편집 거리를 알아보는 프로그램

<환경 설정>
1. 먼저  입력된 문자열에 대한 길이를 획득하고
2. 길이에 맞춰서 이차원 배열을 선언한다.
   이때 문자열이 없는 경우도 포함해서 "길이 + 1" 만큼의 크기로 선언한다.

<부연설명>
행력의 행이 의미하는것은 원본 문자열이고 열이 의미하는것은 목적 문자열이다.
그러니 행의 값이 오르는것은 문자열의 삭제에 대한 cost가 증가하는것을 의미하고
열이 오르는것은 문자열의 추가에 대한 코스트가 증가함을 의미한다.

그리고 갱신의 cost는 실제로의 상황에서는 추가, 삭제가 한꺼번에 일어나는 것이지만 1로 본다.

그래서 문자열의 추가, 삭제, 갱신은 cost가 모두 1이다.

<수행 in geteditdistance>
1. 각 행에 대한 수행

matrix[i][j] = Getmin(matrix[i-1][j] + 1, matrix[i][j-1] + 1, matrix[i-1][j-1] + isreplace);

isreplace는 현재 검사하는 문자가 같을 경우에는 0이고 다를 경우에는 갱신 코스트 1을 추가한다.
처음 부터 인자가 의미하는것은

삭제, 삽입, 갱신에 대한 코스트이다.
그러니까 현재 상태에 오기 직전까지의 모든 최적의 삽입, 삭제, 갱신중에서 가장 작은 값을 현재의 가장 최적해로 지정하는것이다.


http://www.freesearch.pe.kr 고감자

*/

#define MAX_LENGTH	999


int Geteditdistance(int **matrix, char *strFirst, char *strSecond, int flen, int slen);

int Getmin(int ,int, int);

int main(void){
	char strFirst[999];
	char strSecond[999];
	int firstlen;
	int secondlen;
	int **matrix;
	int i, j;
	int retval;

	printf("Input First String : ");
	scanf( "%s",strFirst);

	printf("Input Second String : ");
	scanf("%s",strSecond);

	/* 입력한 문자열에 상응하는 메트릭스 제작 */
	firstlen = strlen(strFirst);
	secondlen = strlen(strSecond);

	matrix = (int**)malloc(sizeof(int*) * (firstlen + 1));

	for(i = 0; i <= firstlen; i++){
		*(matrix + i) = (int*)malloc(sizeof(int) * (secondlen + 1));
	}

	retval = Geteditdistance(matrix, strFirst, strSecond, firstlen + 1, secondlen + 1);

	printf("Edit Distance between \"%s\" and \"%s\" = %d\n\n", strFirst, strSecond,  retval);


	printf("Detail Trace!\n");
	for(i = 0; i <= firstlen;i++){
		for(j = 0;j <= secondlen;j++){
			printf("%d ", matrix[i][j]);
		}
		printf("\n");
	}

	/* 배열 메모리 해제 */
	for(i = 0; i <= firstlen; i++){
		free(matrix[i]);
	}

	free(matrix);
    matrix = NULL;
	return 0;
}


int Geteditdistance(int **matrix, char *strFirst, char *strSecond, int flen, int slen){
	int i,j;
	int isreplace;

	/* 0열과 0행에 대한 초기화  */
	for(i = 0; i < slen; i++){
		matrix[0][i] = i;
	}
	for(i = 0; i < flen; i++){
		matrix[i][0] = i;
	}

	for(i = 1; i < flen; i++){ /* 처음 주어진 문자열의 길이만큼 반복 */

		for(j = 1; j < slen; j++){/* 대상이 되는 문자열의 길이만큼 반복 */
			if( strFirst[i -1] ==  strSecond[j -1]) isreplace = 0;
			else isreplace = 1;
			matrix[i][j] = Getmin(matrix[i-1][j] + 1, matrix[i][j-1] + 1, matrix[i-1][j-1] + isreplace);
		}
	}

	return matrix[flen-1][slen-1];
}


int Getmin(int a,int b, int c){
	int min = INT_MAX;

	if(a < min) min = a;
	if(b < min) min = b;
	if(c < min) min = c;

	return min;
}