String/tests/zfunc.test.cpp

View this file on GitHub
Last update: 2022-12-25 00:11:23+08:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

String/zfunc.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <bits/stdc++.h>
using namespace std;

#include "../zfunc.h"

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    for (auto x : zfunc(s)) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

#line 1 "String/tests/zfunc.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <bits/stdc++.h>
using namespace std;

#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;
*/
#line 7 "String/tests/zfunc.test.cpp"

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    for (auto x : zfunc(s)) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}