String/zfunc.h

• View this file on GitHub
• Last update: 2022-12-25 00:11:23+08:00
• Link: https://judge.yosupo.jp/problem/zalgorithm
• Link: https://oj.vnoi.info/problem/substr

Verified with

• String/tests/zfunc.test.cpp

Code

// z[i] = length of longest common prefix of s[0..N] and s[i..N]
//
// Tested:
// - https://judge.yosupo.jp/problem/zalgorithm
// - (string matching) https://oj.vnoi.info/problem/substr
// Z-func {{{
vector<int> zfunc(const string& s) {
    int n = (int) s.length();
    vector<int> z(n);
    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;
}
// }}}

// Examples:
// Find all occurrences of p in t

/**
    string s = p + "_" + t;
    auto z = zfunc(s);

    REP(i,SZ(t)) {
        if (z[i + SZ(p) + 1] == SZ(p)) {
            cout << 1+i << ' ';
        }
    }
    cout << endl;
*/

#line 1 "String/zfunc.h"
// z[i] = length of longest common prefix of s[0..N] and s[i..N]
//
// Tested:
// - https://judge.yosupo.jp/problem/zalgorithm
// - (string matching) https://oj.vnoi.info/problem/substr
// Z-func {{{
vector<int> zfunc(const string& s) {
    int n = (int) s.length();
    vector<int> z(n);
    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;
}
// }}}

// Examples:
// Find all occurrences of p in t

/**
    string s = p + "_" + t;
    auto z = zfunc(s);

    REP(i,SZ(t)) {
        if (z[i + SZ(p) + 1] == SZ(p)) {
            cout << 1+i << ' ';
        }
    }
    cout << endl;
*/

Back to top page