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: 9 Explanation: For s1 == "b", the longest common prefix is "b" which has a score of 1. For s2 == "ab", there is no common prefix so the score is 0. For s3 == "bab", the longest common prefix is "bab" which has a score of 3. For s4 == "abab", there is no common prefix so the score is 0. For s5 == "babab", the longest common prefix is "babab" which has a score of 5. The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.
Example 2:
Input: s = "azbazbzaz" Output: 14 Explanation: For s2 == "az", the longest common prefix is "az" which has a score of 2. For s6 == "azbzaz", the longest common prefix is "azb" which has a score of 3. For s9 == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9. For all other si, the score is 0. The sum of the scores is 2 + 3 + 9 = 14, so we return 14.
Constraints:
1 <= s.length <= 105
s
consists of lowercase English letters.
Solution: Z-Function
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: long long sumScores(string s) { auto zFunc = [](string_view s) { const int n = s.length(); vector<long long> z(n); for (long long i = 1, l = 0, r = 0; i < n; ++i) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return accumulate(begin(z), end(z), 0LL); }; return zFunc(s) + s.length(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment