Z function

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
307 B
3
Indexable
Never
vector<int> zf(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 && s[z[i]] == s[i + z[i]])
			z[i]++;

		if (i + z[i] - 1 > r)
			l = i, r = i + z[i] - 1;
	}
	return z;
}