Confronto di due stringhe: ottimizzazione del codice

Question

Voglio confrontare due stringhe contando quanti caratteri comuni hanno nella stessa posizione, ma nel complesso in tutti i possibili allineamenti delle due stringhe.

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

Ciò significa che le stringhe str1e str2hanno 3013caratteri comuni in totale in tutti i possibili allineamenti.

Può essere fatto in modo più efficiente, magari senza convertire le stringhe in elenchi?

Answer 1

C'è

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