资讯详情

Z函数（扩展 KMP）

获取字符串 \(s\) 和 \(s[i,n-1]\) （即以 \(s[i]\) 开头的后缀）的最长公共前缀（LCP）的长度，总复杂度 \(\mathcal O(N)\)。

vector<int> zFunction(string s) {int n = s.size();vector<int> z(n);z[0] = n;for (int i = 1, j = 1; i < n; i++) {z[i] = max(0, min(j + z[j] - i, z[i - j]));while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {z[i]++;}if (i + z[i] > j + z[j]) {j = i;}}return z;
}