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; overlapping occurrences count separately.

Return a list of pairs [length, count], one per such prefix, in increasing order of length.

Example 1

Input:  s = "ABACABA"
Output: [[1,4],[3,2],[7,1]]

The borders are "A", "ABA" and "ABACABA". "A" occurs 4 times, "ABA" twice (at positions 0 and 4), and the whole string once.

Example 2

Input:  s = "AAA"
Output: [[1,3],[2,2],[3,1]]

"AA" occurs at positions 0 and 1; the two occurrences overlap and both count.

Example 3

Input:  s = "ABC"
Output: [[3,1]]

No proper prefix is also a suffix, so only s itself is reported.

Constraints

• 1 <= s.length <= 10^5
• s consists of English letters.