Occurrence counts of prefixes that are also suffixes

Problem 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.