}The binary string operator weave (|) interleaves the characters from its operands. The result is the first character of the left operand, followed by the first character of the right operand, followed by the second character of the left operand, and then the second charater of the right operand, and so on, until no more characters exist.
For example, abc|defgh produces adbecfgh, and defgh|abc produces daebfcgh.
Given two sets of strings, whose size are n and m, a larger set of size n×m is created by producing all possible weaves, selecting one string from each set. Call this large set a weaving.
The similarity of two strings is the number of positions at which they have matching characters.
For example, the similarity of abdecfgh and deabfcgh is 2, while the similarity of abc and aaaaaa is 1.
Given two sets of strings, create a program to determine the total similarity of neighboring strings in the sorted weaving.
Each dataset is a text file containing lines of ASCII text containing only lower-case letters. A blank line separates the two sets of strings. The length of each line is between 1 and 10,000 characters inclusive.
a abc bcd aa def xxxxx baba
The example dataset above contains two sets (a,abc,bcd and aa,def,xxxxx,baba). They producing the following weaving (shown in a grid to emphasize construction).
aaa aabac bacad adef adbecf bdcedf axxxxx axbxcxxx bxcxdxxx ababa abbacba bbcadba
Sorting the weaving produces the following sequence (with similarity for adjacent pairs of strings).
aaa 0 (no previous neighbor) aabac 2 ababa 1 abbacba 2 adbecf 3 adef 2 axbxcxxx 1 axxxxx 4 bacad 0 bbcadba 4 bdcedf 3 bxcxdxxx 3
Thus the total similarity is 0+2+1+2+3+2+1+4+0+4+3+3 = 24 for this example.
Your program should determine the total similary for the weaving of the sets of string given, and report this as shown below.
{
"answer" : 24
}