Donc en fait ça voudrait dire fabriquer une fonction g aléatoire de E dans l'ensemble des entiers à m bits, telle que g(i) a toujours k bits à 1.
Alors le hash d'une chaîne est le OR des g(i) pour tout élément i de la chaîne.
Réunir deux chaînes se résume à faire un OR, et tester l'inclusion est facile aussi.

Ah, c'est splendide. Clair, élégant et rapide.
Ne reste qu'à trouver m et k pour qu'il n'y ait pas trop de collisions et pas trop de faux positifs.
Comme le go ajoute plein de contraintes pratiques (les éléments d'une chaîne sont assez "localisés" puisqu'adjacents, une chaîne a dans la plupart des cas moins de 10-15 éléments, et dans le pire des cas moins de 50), ça doit être possible d'avoir une solution bien.

Joie.