1vector<int> z_function(string s) {
2 int n = (int) s.length();
3 vector<int> z(n);
4 for (int i = 1, l = 0, r = 0; i < n; ++i) {
5 if (i <= r)
6 z[i] = min (r - i + 1, z[i - l]);
7 while (i + z[i] < n && s[z[i]] == s[i + z[i]])
8 ++z[i];
9 if (i + z[i] - 1 > r)
10 l = i, r = i + z[i] - 1;
11 }
12 return z;
13}
14