File Anagrams.h

↰ Parent directory (ADS/string)

The classes of anagrams among n words of length at most k: two words are anagrams if one is a permutation of the other.

Definition (ADS/string/Anagrams.h)

Detailed Description

anagramGroups() gives the signature of each word, its items sorted, and gathers the words of equal signature in a hash table, :math:` O( n k log k ) ` expected time and O( n k ) space; the groups come in the order of their first word, and the words of a group in their order. The signature by counting sort over an alphabet of :math:` sigma ` symbols, or the vector of the counts of the symbols, costs :math:` O( k + sigma ) ` per word instead; sorting the pairs ( signature , word ) in place of hashing them gives the classes in :math:` O( n k log n ) ` worst-case time.

anagramGroups() takes the words as any sequence S with an iterator constructor, sortable items and a hash, std::hash< S > by default; the overload on std::string also takes a list of literals.

The contracts [see File Contract.h]: the groups partition the words, and the words of a group are anagrams of its first (an audit). The functions are defined in Anagrams.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

  1. Bentley, Programming Pearls, 2nd ed., Addison-Wesley, 2000, column 2

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions