← all categories

Z Function db694547

Z-function z[i] = length of the longest common prefix of s and s[i..]. z[0] is conventionally left 0 (undefined/unused). For substring search, same trick as KMP: run on pattern + '#' + text and scan for z[i] == |pattern|.

Time: O(n). tested

content/strings/z-function.h

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