2223. Sum of Scores of Built Strings Hard

1/**
2 * [2223] Sum of Scores of Built Strings
3 *
4 * 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.
5 * 
6 * 	For example, for s = "abaca", s1 == "a", s2 == "ca", s3 == "aca", etc.
7 * 
8 * The score of si is the length of the longest common prefix between si and sn (Note that s == sn).
9 * Given the final string s, return the sum of the score of every si.
10 *  
11 * Example 1:
12 * 
13 * Input: s = "babab"
14 * Output: 9
15 * Explanation:
16 * For s1 == "b", the longest common prefix is "b" which has a score of 1.
17 * For s2 == "ab", there is no common prefix so the score is 0.
18 * For s3 == "bab", the longest common prefix is "bab" which has a score of 3.
19 * For s4 == "abab", there is no common prefix so the score is 0.
20 * For s5 == "babab", the longest common prefix is "babab" which has a score of 5.
21 * The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.
22 * Example 2:
23 * 
24 * Input: s = "azbazbzaz"
25 * Output: 14
26 * Explanation: 
27 * For s2 == "az", the longest common prefix is "az" which has a score of 2.
28 * For s6 == "azbzaz", the longest common prefix is "azb" which has a score of 3.
29 * For s9 == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9.
30 * For all other si, the score is 0.
31 * The sum of the scores is 2 + 3 + 9 = 14, so we return 14.
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	1 <= s.length <= 10^5
37 * 	s consists of lowercase English letters.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/sum-of-scores-of-built-strings/
43// discuss: https://leetcode.com/problems/sum-of-scores-of-built-strings/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn sum_scores(s: String) -> i64 {
49        
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_2223() {
61    }
62}
63