test/yosupo/zalgorithm.test.cpp

View this file on GitHub
Last update: 2024-01-07 22:05:53+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

Z Array (string/z_array.hpp)

Code

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

#include <bits/stdc++.h>

#include "../../string/z_array.hpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string S;
    cin >> S;
    vector<int> z = z_array(S);
    for (int i = 0; i < S.size(); ++i)
        cout << z[i] << (i < S.size() - 1 ? " " : "\n");
}

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

#include <bits/stdc++.h>

#line 4 "string/z_array.hpp"

std::vector<int> z_array(const std::string& s) {
    const int n = s.size();
    std::vector<int> z(n);
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        int k = i - l;
        if (i <= r && z[k] < r - i + 1) {
            z[i] = z[k];
        } else {
            l = i;
            if (i > r) r = i;
            while (r < n && s[r - l] == s[r]) ++r;
            --r;
            z[i] = r - l + 1;
        }
    }
    return z;
}
#line 6 "test/yosupo/zalgorithm.test.cpp"
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string S;
    cin >> S;
    vector<int> z = z_array(S);
    for (int i = 0; i < S.size(); ++i)
        cout << z[i] << (i < S.size() - 1 ? " " : "\n");
}