A songbird's call is recorded as a string song of lowercase letters, one per note. From any
later note the bird may start echoing its opening. The echo at position i (for
1 <= i < len(song)) is the number of notes, starting at i, that match the opening note for
note: the largest L with song[i:i+L] == song[:L].
Write echo_total(song) that returns the sum of the echoes over all positions 1 to
len(song) - 1.
Examples
Input: song = "abacaba"
Output: 5
Explanation: echoes are 0, 1, 0, 3, 0, 1 at positions 1..6 ("a", "aba" and "a" match the opening).
Input: song = "aaaa"
Output: 6
Explanation: 3 + 2 + 1.
Input: song = "abab"
Output: 2
Constraints
0 <= len(song) <= 2 * 10**5; an empty or one-note song has total0- Target: about O(n) time; songs can be extremely repetitive
Goals
- Define a per-position match length against the start of the text
- Reuse a match already found instead of rescanning the same characters
- Keep the total work linear on highly repetitive text