- Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathmatch_z.cpp
More file actions
Latest commit
19 lines (18 loc) · 620 Bytes
/
Copy pathmatch_z.cpp
File metadata and controls
19 lines (18 loc) · 620 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include"../0-common/common.hpp"
// what: compute prefix match lengths for each position in a string.
// time: O(n); memory: O(n)
// constraint: z[0]=n, 0-indexed string.
// usage: auto z = z_func(s);
vector<int> z_func(const string &s) {
// result: z[i] = longest prefix length matching s[i..].
int n = sz(s);
vector<int> z(n);
if (!n) return z;
z[0] = 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;
}