\(0 \leq k \leq \min(A, B, C)\) に対し、次の手順で A, B, C をそれぞれ \(A\), \(B\), \(C\) 個含む文字列を作ることを考えます。

1. A, B, C をそれぞれ \(A-k\), \(B-k\), \(C-k\) 個含む文字列を一つとる。
2. この文字列の文字と文字の間、あるいは先頭ないし末尾から挿入位置を重複を許して \(k\) 個選び、それら挿入位置に ABC, BCA, CAB のいずれかを挿入する。ただし、ABC, BCA, CAB はそれぞれ C, A, B の直後には挿入しない。

2 の手順で、挿入位置を固定したとき、挿入する文字列を ABC, BCA, CAB の中から選ぶ場合の数は、次のように求められます。

• 挿入位置が文字列の先頭を含む場合、\(3 \cdot 2^{k-1}\) （先頭は ABC, BCA, CAB のいずれを選んでもよく、先頭以外は直前の文字ごとにちょうど \(2\) 通りの選び方があるため）
• 挿入位置が文字列の先頭を含まない場合、\(2^k\)

1 の場合の数および 2 の挿入位置の選び方は簡単に求められるので、上の場合の数をすべての \(k\) に対して求めるのは \(O(A+B+C)\) で可能です。

部分文字列として現れる ABC, BCA, CAB であって、それぞれ C, A, B の直後にあるようなものではないものを考えます。上の手順で挿入した ABC, BCA, CAB は必ずこの性質を持っていることに注意すると、このような部分文字列を \(j\) 個持つ文字列は、上の手順で \(\binom{j}{k}\) 回 重複して数えられることがわかります。よって、包除原理を使って問題の答えを求めることができます。