# Comparing two strings - code optimization

I want to compare two strings by counting how many common characters they have at the same position - but overall in all possible alignments of the two strings.

SeedRandom[1]
str1 = RandomInteger[{1, 26}, 90] /.
Thread[Range[26] -> CharacterRange["A", "Z"]] // StringJoin
str2 = RandomInteger[{1, 26}, 850] /.
Thread[Range[26] -> CharacterRange["A", "Z"]] // StringJoin
fu[x_, y_] :=
Module[{par = Partition[Characters[y], StringLength[x], 1, {1, 1}]},
Count[Flatten[(Transpose[{#, Characters[x]}] & /@ par), 1], {z_, z_}]
]

fu[str1, str2] // Timing
(*{0.046875, 3013}*)

This means that strings str1 and str2 have 3013 common characters in total in all possible alignments.

Can it be done more efficiently, perhaps without converting strings into lists?

• Is this the same as doing {c1, c2} = Characters /@ {str1, str2}; Sum[Boole[c1[[i]] == c2[[j]]], {i, Length[c1]}, {j, Length[c2]}] which also gives 3013? Or more compactly you could do Total[Outer[Boole@*Equal, c1, c2], 2] Oct 3 '20 at 17:53
• ^ note with the above, if you use ToCharacterCode instead of Characters, you get slightly better performance. Oct 3 '20 at 18:02
• I got an order of a magnitude's speed-up using fu[x_, y_] := Module[{ par = Partition[Characters[y], StringLength[x], 1, {1, 1}], len = StringLength[x] }, Total[len - HammingDistance[x, StringJoin[#]] & /@ par] ] Oct 3 '20 at 18:06
• @flinty: Your code is more elegant but no speed gain. C. E.@: Nice speed gain. Oct 3 '20 at 19:00
• You could try to use ListCorrelate: ListCorrelate[str1, str2, {1, -1}, {}, (Equal[##]) &,(Count[{##}, True]) &] Oct 4 '20 at 16:00