「字符串」Z函数（扩展KMP|exKMP）/ LeetCode 2223（C++）
目录
概述
核心概念：z[i]
思路
算法过程
Code
概述
LeetCode 2223：
你需要从空字符串开始 构造 一个长度为
n的字符串s，构造的过程为每次给当前字符串 前面 添加 一个 字符。构造过程中得到的所有字符串编号为1到n，其中长度为i的字符串编号为si。
- 比方说，
s = "abaca"，s1 == "a"，s2 == "ca"，s3 == "aca"依次类推。
si的 得分 为si和sn的 最长公共前缀 的长度（注意s == sn）。给你最终的字符串
s，请你返回每一个si的 得分之和 。示例 1：
输入：s = "babab" 输出：9 解释： s1 == "b" ，最长公共前缀是 "b" ，得分为 1 。 s2 == "ab" ，没有公共前缀，得分为 0 。 s3 == "bab" ，最长公共前缀为 "bab" ，得分为 3 。 s4 == "abab" ，没有公共前缀，得分为 0 。 s5 == "babab" ，最长公共前缀为 "babab" ，得分为 5 。 得分和为 1 + 0 + 3 + 0 + 5 = 9 ，所以我们返回 9 。
Z函数是一种独到的匹配算法，虽然国内称之为扩展KMP，其实他更具有Manacher算法的特征。
与KMP类似的是，它也是字符串自匹配问题：
KMP_next：next[i]表示[0,i-1]子串的最长公共前后缀长度。
Z_function：z[i]表示[0,n)完整串与[i,n)子串的最长公共前缀长度（即LCP）。
Z函数基于主串与他的后缀串[i,n)大做文章。
核心概念：z[i]
Z_function：z[i]表示[0,n)完整串与[i,n)子串的最长公共前缀（即LCP）。
我们来形象理解一下这句话：
i 0 1 2 3 4 5 6
char s[i] = -------------└str┘---------└str┘
对于从i=2开始的子串，其与主串有相同的前缀str，长度为3，故z[2]=3具体地，
i 0 1 2 3 4 5 6
char s[i] = a b a c a b a
int z[i] = 0 0 1 0 3 0 1*注意*：约定z[0]=0。
思路
LeetCode 2223：题意很明显，就是要我们求这个主串的z函数，然后累加求和。
暴力的做法很容易想到，但我们提供一种更优越的做法：Z-box操作。
我们上文提到z函数很像manacher算法，也正因如此，这是一种维护已知量使得时间复杂度到达线性级别的算法。
算法过程
接下来我们称最长公共前缀为LCP。
我们维护Z-box区间l和r双指针，初始值为l=r=0，
我们设计Z-box总是维护已知的最大子串LCP的两端。
i 0 1 2 3 4 5 6 7
char s[i] = ---------------|s[2,n) -----------└Z-box┘l r
int z[i] = 0 2 4 ?
遍历到i=4时，此前已知的最长z[2]=4
故Z-box维护这个区间，有l=2，r=5;考虑当我们遍历到下标i时，若其处于z-box中(l<=i<=r)，那么它可以对应到原始主串的i-r下标处。
这是因为z[i]表示[0,n)完整串与[i,n)子串的LCP，而z-box维护最长z[i]的端点l和r，那么对于l<=i<=r，s[i]==s[i-l]。
因此我们就可以直接利用此前已知的z函数值推断未知值。
有两种情况（其中一种有三种小情况）需要讨论：
1.i<=r,此时z[i]至少>= min(z[i - l], r - i + 1);
有以下三种小情况，观察下图，结合z函数定义，注意* ^ ~这三个位置：
①z[i-l]<r-i+1，即i对应点最长延伸严格小于Z-box对应区的右边界
i=3时,注意* ^ ~这三个位置 i 3 |
char s[i] = ---------------└z[j]┘*└z[j]┘^ //j=i-l;└-Z-box-┘s[2,n) -----------└z[i]┘~└-Z-box-┘l r
*与^必不同
^与~必相同
故*与~必不同,此时z[i]=z[i-l];此时z[i]=z[i-l];
②z[i-l]=r-i+1，即i对应点最长延伸恰好压线Z-box对应区的右边界
注意* ^ ~这三个位置i 3|
char s[i] = ---------------└-z[j]┘*└-z[j]┘^ //j=i-l;└-Z-box-┘s[2,n) -----------└-z[i]┘~└-Z-box-┘l r
*与^必不同
^与~必不同
^与~可能相同,z[i]>=z[i-l];此时z[i]=z[i-l],随后暴力扩展z[i];
③z[i-l]>r-i+1
注意* ^ ~这三个位置i 3|
char s[i] = ---------------└-z[j]-┘*└-z[j]-┘ //j=i-l;└-Z-box-┘^s[2,n) -----------└z[i]-┘~└-Z-box-┘l r
*与^必相同
^与~必不同
故*与~必不同，此时被截断一部分，z[i]=r - i + 1;此时z[i]=r - i + 1;
2.i>r
不用看图，这种情况直接暴力扩展z[i]即可。
综合以上情况，我们能写下以下代码：
vector<int> Z_algorithm(const string& s) {const int n = s.size();vector<int> z(s.size(), 0);for(int i = 1, l = 0, r = 0; i < n; i++) {if (i <= r)z[i] = min(z[i - l], r - i + 1);//i<=r时执行操作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;//更新Z-box}return z;
}*注意*：我们在代码层面虽然对于任意的i都会进入暴力扩展while循环，但对于不需要暴力的情况，while会直接跳出。
Code
class Solution {
public:vector<int> Z_algorithm(const string& s) {const int n = s.size();vector<int> z(s.size(), 0);for (int i = 1, l = 0, r = 0; i < n; i++) {if (i <= r)z[i] = min(z[i - l], r - i + 1);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 z;}long long sumScores(string s) {vector<int>&& ans = Z_algorithm(s);ans[0] = s.size();return accumulate(ans.begin(), ans.end(), 0ll);}
};