Sum of Scores of Built Strings
You are building a string s of length n one character at a time, prepending each new character to the front of the string. The strings are labeled from 1 to n, where the string with length i is labeled si.
For example, for s = "abaca", s1 == "a", s2 == "ca", s3 == "aca", etc.
The score of si is the length of the longest common prefix between si and sn. Note that s == sn.
Given the final string s, return the sum of the score of every si.
Example 1
Input
s = "babab"Output
9The scores are 1, 0, 3, 0, and 5, so their sum is 9.
Example 2
Input
s = "azbazbzaz"Output
14Only s2, s6, and s9 have nonzero scores of 2, 3, and 9, so their sum is 14.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.