Comparaison de deux chaînes - optimisation du code

Question

Je veux comparer deux chaînes en comptant le nombre de caractères communs qu'elles ont à la même position - mais globalement dans tous les alignements possibles des deux chaînes.

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}*)

Cela signifie que les chaînes str1et str2ont 3013des caractères communs au total dans tous les alignements possibles.

Cela peut-il être fait plus efficacement, peut-être sans convertir les chaînes en listes?

Answer 1

Il y a

fu3 = Dot @@ Lookup[#, Union @@ Keys[#], 0] &[Counts@*ToCharacterCode /@ {#, #2}] &;

Last@Table[fu[str1, str2], {100}] // RepeatedTiming
Last@Table[fu3[str1, str2], {100}] // RepeatedTiming
(* {2.3, 3013} *)
(* {0.0029, 3013} *)