Occurrence counts of prefixes that are also suffixes

Given a string s, consider the set of all prefixes of s that are simultaneously suffixes of s (its borders, including s itself). For each such prefix, report how many times it occurs as a substring of s. Return the prefixes (by length) together with their occurrence counts.

Input / Output

• Input: string s.
• Output: for each prefix that is also a suffix (in increasing length order), its length and the number of occurrences of that prefix as a substring of s.

Constraints

• 1 <= |s| <= 10^5
• Small alphabet (e.g. lowercase/uppercase letters).

Example

• s = "ABACABA" → borders of lengths 1 ("A"), 3 ("ABA"), 7 ("ABACABA"); occurrence counts 4, 2, 1.

Expected approach

• Compute the prefix function (KMP) or Z-function of s.
• The prefixes that are also suffixes come from walking the failure chain from position n: fail[n] -> fail[fail[n]] -> …, plus the whole string.
• Using the Z-array, do cnt[z[i]]++ then suffix-accumulate so cnt[L] counts substrings of length L equal to the prefix; add 1 for the prefix itself.
• O(n) overall.