content/string/z.cpp


1
2
3
4
5
6
7
8
9
10

vector<int> Z(const string& s) {
	int n = ssize(s);
	vector<int> z(n);
	for (int i = 1, x = 0; i < n; i++) {
		z[i] = max(0, min(z[i - x], x + z[x] - i));
		while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
			x = i, z[i]++;
	}}
	return z;
}