2223. 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.

class Solution {
    long long zFunction(string& s) {
        int n = s.length();
        vector<int> z(n);
        for(int 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 and 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);
    }
public:
    long long sumScores(string s) {
        return zFunction(s) + s.length();
    }
};