Compute the total score of a string by summing the lengths of the longest common prefix between the string and each of its suffixes.
Given a string , define the score of a suffix as the length of the longest common prefix between and . The score of the whole string is the sum of the scores of all suffixes.
Your task is to return that total score.
This is a string-matching style problem: for every starting position, compare the suffix against the original string and accumulate the prefix match length.
Input Format
- A single string .
- The string contains only lowercase English letters.
Output Format
- Return one integer: the sum of scores of all suffixes of .
Constraints
- contains only lowercase English letters.
- The answer may not fit in 32-bit integer arithmetic.
Example 1
Input
s = "babab"
Output
9
Explanation
Suffix scores are:
- "babab" vs "babab" -> 5
- "abab" vs "babab" -> 0
- "bab" vs "babab" -> 3
- "ab" vs "babab" -> 0
- "b" vs "babab" -> 1 Total = 5 + 0 + 3 + 0 + 1 = 9.
Example 2
Input
s = "aaaaa"
Output
15
Explanation
Every suffix matches the full prefix as much as possible: 5 + 4 + 3 + 2 + 1 = 15.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.