Approximate String Matching

Deciding whether two words are identical is easy, since you only compare them letter by letter. Deciding whether two words are almost identical is harder, and it needs a definition of how close "almost" is.

There are many ways to match words approximately. One of them is the best substring match. Line the two words up position by position, count the letters that agree, and take the alignment that makes that count as large as possible. The two words may be offset by any amount. Take CAPILLARY and MARSUPIAL. Stacking them as they are gives this.

CAPILLARY
MARSUPIAL

Only one letter agrees (A). Sliding one word along does better.

CAPILLARY
     MARSUPIAL

Two letters agree now (A and R). The best alignment is this one.

   CAPILLARY
MARSUPIAL

Three letters agree (P, I and L).

Let $c$ be the number of agreeing letters in the best alignment. The approximation measure of two words $w_1$ and $w_2$ is

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

For the example above, appx(CAPILLARY, MARSUPIAL) = 6/(9+9) = 1/3. Every word W satisfies appx(W, W) = 1, and two words that never agree in any position have an appx value of 0.

The input is a series of lines. Each line holds two words separated by one space, and every word is uppercase. A line holding only -1 ends the input, and that line is not a pair of words.

For each pair of words, print one line with the appx value written as a reduced fraction.

appx(word1,word2) = value

The two words are separated by a single comma with no space, and the equals sign has one space on each side. When the fraction reduces to 0 or 1, print 0 or 1 with no denominator.