Combinatorics on words is the mathematical study of words, which is the foundation for stringology (algorithms on strings/words). The two main branches of this are:

1. Analysis of words

For example, a square-free word is a word in which no sub-word is a square. A square is a word of the form uu, where u is a sub-word which is repeated twice consecutively. When looking at a binary alphabet {a, b}, the only square-free words which can built upon this are a, b, ab, ba, aba and bab. The strings aa, bb, aab, abb, aaa, bbb, abab, baba (and so on) contain squares (in bold).

2. How words can be visualised

For example, the word banana can be represented by its suffix tree, shown below. (I will post a DOTD for suffix trees tomorrow!)

[1]

Please reload

Please reload