TAOCP 7.2.2 Exercise 35
Let $A$ be an alphabet of size $m$.
Exercise 35. ▶ [22] [22] Let $w_1, w_2, \ldots, w_n$ be four-letter words on an $m$-letter alphabet. Design an algorithm that accepts or rejects each $w_j$, according as $w_j$ is commafree or not with respect to the accepted words of ${w_1, \ldots, w_{j-1}}$.
Verified: yes
Solve time: 3m44s
Let $A$ be an alphabet of size $m$. A set $S$ of four-letter words is commafree if for any $x,y \in S$, no length-4 substring of the concatenation $xy$ that overlaps the boundary between $x$ and $y$ is itself in $S$. Equivalently, every factorization ambiguity of length-4 blocks is forbidden.
We are given accepted words $S_{j-1} = {w_1,\dots,w_{j-1}}$, assumed already commafree, and we must decide whether $w_j$ can be added so that $S_{j-1} \cup {w_j}$ remains commafree.
Structure of possible overlaps
Let $x = a_1a_2a_3a_4$ and $y = b_1b_2b_3b_4$. The length-4 substrings of $xy$ that can cross the boundary are exactly:
$$ a_2a_3a_4b_1,\quad a_3a_4b_1b_2,\quad a_4b_1b_2b_3. $$
These are the only new substrings created by concatenation.
Condition for safe insertion
A word $w = w_1w_2w_3w_4$ is acceptable if and only if no word in $S_{j-1} \cup {w}$ appears as a boundary-crossing substring in any concatenation of two words from $S_{j-1} \cup {w}$.
Since $S_{j-1}$ is already commafree, only concatenations involving $w$ can introduce violations. We therefore check the three cases:
Case 1: $u w$, where $u \in S_{j-1}$
Boundary substrings:
$$ u_2u_3u_4w_1,\quad u_3u_4w_1w_2,\quad u_4w_1w_2w_3. $$
Each must not lie in $S_{j-1} \cup {w}$.
Case 2: $w v$, where $v \in S_{j-1}$
Boundary substrings:
$$ w_2w_3w_4v_1,\quad w_3w_4v_1v_2,\quad w_4v_1v_2v_3. $$
Each must not lie in $S_{j-1} \cup {w}$.
Case 3: $w w$
Boundary substrings:
$$ w_2w_3w_4w_1,\quad w_3w_4w_1w_2,\quad w_4w_1w_2w_3. $$
Each must not lie in $S_{j-1} \cup {w}$.
Algorithm
Maintain a dictionary (hash set) $H$ containing all accepted words.
For each incoming word $w_j$:
- Initialize a flag $\text{ok} \leftarrow \text{true}$.
- For each $u \in S_{j-1}$, test the three substrings of $u w_j$. If any belongs to $H$, set $\text{ok} \leftarrow \text{false}$.
- For each $v \in S_{j-1}$, test the three substrings of $w_j v$. If any belongs to $H$, set $\text{ok} \leftarrow \text{false}$.
- Test the three substrings of $w_j w_j$. If any belongs to $H$, set $\text{ok} \leftarrow \text{false}$.
- If $\text{ok}$, accept $w_j$ and insert it into $H$. Otherwise reject $w_j$.
Correctness
Assume $S_{j-1}$ is commafree.
If the algorithm rejects $w_j$, then some boundary substring formed in $u w_j$, $w_j v$, or $w_j w_j$ equals a word already in $S_{j-1}$ or equals $w_j$. In either case, adding $w_j$ creates a concatenation of two words in the enlarged set whose boundary-crossing substring lies in the set itself, violating commafreeness.
Conversely, if adding $w_j$ makes the set non-commafree, then there exist $x,y \in S_{j-1} \cup {w_j}$ such that a boundary substring of $xy$ equals some word in $S_{j-1} \cup {w_j}$. Since $S_{j-1}$ was already commafree, at least one of $x$ or $y$ must be $w_j$, so the offending substring is one of those explicitly tested by the algorithm. Hence the algorithm will reject $w_j$.
Thus the algorithm accepts exactly those words that preserve commafreeness.
Complexity
Each word $w_j$ is compared against all words in $S_{j-1}$, and each comparison checks three substrings in constant time. With hashing, membership tests are $O(1)$, so the total cost for $w_j$ is $O(|S_{j-1}|)$, and the full process is $O(n^2)$ time in the number of words.
This gives a complete incremental decision procedure for commafree four-letter codes.