How Often Each Prefix Appears — Solution & Editorial

Back to the Problem

From the prefix function π, each position contributes to prefix π[i]; propagate counts down the failure links (cnt[π[k−1]] += cnt[k]) and add 1 for each prefix's own occurrence.

Complexity: O(|S|)

Watch out: Failure-link counts must be accumulated from long to short prefixes, or shorter prefixes undercount.