문자열 근사 매칭

두 단어가 완전히 같은지 알아내기는 쉽다. 글자를 하나씩 비교하면 된다. 두 단어가 거의 같은지 알아내기는 그보다 어렵고, 먼저 "거의"가 얼마나 가까운 것인지부터 정해야 한다.

단어를 근사적으로 비교하는 방법은 여러 가지가 있다. 그중 하나가 최선의 부분 일치를 찾는 방법이다. 두 단어를 자리마다 맞대어 놓고 같은 자리에서 일치하는 글자의 개수를 센 다음, 그 개수가 가장 커지는 배치를 고른다. 두 단어는 어느 만큼 어긋나게 겹쳐도 된다. CAPILLARY와 MARSUPIAL을 예로 들자. 그대로 위아래에 놓으면 다음과 같다.

CAPILLARY
MARSUPIAL

일치하는 글자는 A 하나뿐이다. 한쪽을 밀어서 겹치면 더 낫다.

CAPILLARY
     MARSUPIAL

이번에는 A와 R, 두 글자가 일치한다. 가장 좋은 배치는 다음과 같다.

   CAPILLARY
MARSUPIAL

여기서는 P, I, L 세 글자가 일치한다.

가장 좋은 배치에서 일치하는 글자의 개수를 $c$라고 하면, 두 단어 $w_1$과 $w_2$의 근사도는 다음과 같다.

$\mathrm{appx}(w_1, w_2) = \frac{2c}{|w_1| + |w_2|}$

위 예에서는 appx(CAPILLARY, MARSUPIAL) = 6/(9+9) = 1/3이다. 어떤 단어 W에 대해서도 appx(W, W) = 1이고, 어느 자리에서도 글자가 일치하지 않는 두 단어의 appx 값은 0이다.

입력은 여러 줄로 이루어진다. 각 줄에는 대문자로만 이루어진 단어 두 개가 공백 하나를 사이에 두고 주어진다. -1만 적힌 줄이 나오면 입력이 끝나며, 그 줄은 단어 쌍이 아니다.

단어 쌍마다 한 줄씩 appx 값을 기약분수로 출력한다.

appx(word1,word2) = 값

두 단어 사이에는 쉼표 하나만 넣고 공백은 넣지 않는다. 등호 앞뒤에는 공백을 하나씩 둔다. 분수가 0이나 1로 약분되면 분모 없이 0 또는 1만 출력한다.