One 、 Title Description

Two 、 Algorithm

This question is actually the subject of investigation Z Algorithm .

1、 Generalized problem description

For a length of $n$ String $s$. Defined function $z[i]$ Express $s$ and $s[i:n-1]$ The length of the longest common prefix . Give the calculation
$z$ The algorithm of . notes ： here $s[i:n-1]$ contain $s[i]$ and $s[n-1]$.

2、 analysis

And KMP similar , Calculation $z[i]$ We need to use the experience of the previous calculation process . The core of this algorithm is ： Maintained $[l,r]$ Section , Satisfy $$r=\underset{0\le k<i}{\max }k+z[k]-1\text{\hspace{1em}(1)}$$$$l+z[l]-1=r\text{\hspace{1em}(2)}$$
It's not hard to find out ,$[l,r]$ It's actually $s$ and $s[l:n-1]$ The longest common prefix interval of . therefore , We can get $$s[0:r-l]=s[l:r]\text{\hspace{1em}(3)}$$
When we need to calculate $z[i]$ when , It needs to be discussed on a case by case basis ：
（1） If $i\le r$, Yes (3) Add... To the starting interval at the left and right ends of the equation at the same time $i-l$ You can get $$s[i-l:r-l]=s[i:r]\text{\hspace{1em}(4)}$$
（a） if $z[i-l]<r-i+1$, that $$s[i-l:i-l+z[i-l]-1]=s[i:i+z[i-l]-1]=s[0:z[i-l]-1]\text{\hspace{1em}(5)}$$$$s[i-l+z[i-l]]=s[i+z[i-l]]\ne s[z[i-l]]\text{\hspace{1em}(6)}$$
therefore $$z[i]=z[i-l]\text{\hspace{1em}(7)}$$
（b） if $z[i-l]\ge r-i+1$, Then we can expand (4) type $$s[i-l:r-l]=s[i:r]=s[0:r-i]\text{\hspace{1em}(8)}$$
At this time, we enumerate the following characters ： $$z[i]=r-i+1+(s[r:n-1]Ands[r-i+1:n-1]OfmostLongMalecommonfrontAffixDistrictbetweenLongdegree)\text{\hspace{1em}(9)}$$
（2） If $i>r$, It indicates that you have not visited $s[i]$, So let's go straight from $s[i]$ Start solving violence .
We need to pay attention to , After each treatment , You need to judge whether to update $[l,r]$ Section .

3、 Realization

vector<int> z_function(string s) {
    
    int sLength = s.length(), left = 0, right = 0;
    vector<int> z(sLength);
    for (int i = 1; i < sLength; ++i) {
    
        if (i <= right) {
    
            if (z[i - left] < right - i + 1) {
    
                z[i] = z[i - left];
            }
            else {
    
                z[i] = right - i + 1;

                while (i + z[i] < sLength && s[i + z[i]] == s[z[i]]) {
    
                    ++z[i];
                }
            }
        }
        else {
    
            z[i] = 0;

            while (i + z[i] < sLength && s[i + z[i]] == s[z[i]]) {
    
                ++z[i];
            }
        }

        if (i + z[i] - 1 > right) {
    
            left = i;
            right = i + z[i] - 1;
        }
    }

    return z;
}

It's not hard to find out , Two else Branches can merge . therefore , The code can be reduced to ：

vector<int> z_function(string s) {
    
	int sLength= s.length(), left = 0, right = 0;
	vector<int> z(sLength);
	for (int i = 1; i < sLength; ++i) {
    
		if (i <= right && z[i - left] < right - i + 1) {
    
			z[i] = z[i - left];
		}
		else {
    
			z[i] = max(0, right - i + 1);

			while (i + z[i] < sLength && s[i + z[i]] == s[z[i]]) {
    
				++z[i];
			}
		}

		if (i + z[i] - 1 > right) {
    
			left = i;
			right = i + z[i] - 1;
		}
	}

	return z;
}

The above code is derived from $i=1$ Start calculating $z[i]$ Because $i=0$ Corresponding $[l,r]$ Interval is $[0,n-1]$, It is equivalent to solving by violence .

sumScores The implementation is as follows ：

long long sumScores(string s) {
    
    auto z = z_function(s);
    return accumulate(z.begin(), z.end(), (long long)0) + s.length();
}