WordWorks

Interactive Combinatorics on Words and String Algorithms

Words, factors, and borders — taught through interactive visualizations and generated practice with explanation-based feedback.

Foundations

  1. Lesson 1WordsAlphabets, words, length, the empty word, concatenation, and 1-based indexing.
  2. Lesson 2FactorsFactors, prefixes, suffixes, proper factors, and occurrences.
  3. Lesson 3BordersBorders, bordered and unbordered words, and the longest and shortest border.Practice →

Combinatorics

  1. Lesson 4Counting Unbordered WordsThe Nielsen recurrence for counting unbordered words over a k-letter alphabet.Practice →
  2. Lesson 5Generating Unbordered WordsA constant-amortized algorithm (GenU) that generates every unbordered word of a given length.Practice →
  3. Lesson 6Generating Bordered WordsA constant-amortized algorithm (GenB) that generates every bordered word of a given length, via the fact that the shortest border of a bordered word is unbordered.Practice →

Algorithms

  1. Lesson 6KMP and the Prefix FunctionLinear-time string matching, the prefix function, and linear-time unbordered detection.Practice →
  2. Lesson 7Periods and PowersPeriods of words, the least period via the prefix function, powers, and the primitive root.Practice →

Advanced Topics

  1. Lesson 8Factor AvoidanceCounting words that avoid a pattern using a deterministic finite automaton built from the failure function.Practice →
  2. Lesson 9Autocorrelation and the Guibas–Odlyzko FormulaThe autocorrelation word, the overlap set B(P), and two counting identities for words avoiding a single pattern.Practice →
  3. Lesson 10Cross-BordersWords that bridge a pair — cross-borders, the shortest cross-border, and a guided proof that it is unbordered.Practice →