Test/yosupo-Z-Algorithm.test.cpp

• View this file on GitHub
• Last update: 2023-07-12 13:28:30+00:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• Zalgorithm (String/Zalgorithm.hpp)

Code

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

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

#include "../String/Zalgorithm.hpp"

int main() {

    string S;
    cin >> S;
    vector<int> Z = Zalgorithm(S);
    for(int i = 0; i < (int)(Z.size()); i++) {
        cout << Z[i] << " ";
    }
    cout << endl;

}

#line 1 "Test/yosupo-Z-Algorithm.test.cpp"
#include<bits/stdc++.h>
using namespace std;

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

#line 1 "String/Zalgorithm.hpp"
vector<int> Zalgorithm(const string &S) {
    vector<int> Z(S.size());
    Z[0] = (int)S.size();
    int i = 1, j = 0;
    while(i < S.size()) {
        while(i + j < (int)(S.size()) && S[j] == S[i + j]) j++;
        Z[i] = j;

        if(j == 0) {
            i++;
            continue;
        }

        int k = 1;
        while(k < j && k + Z[k] < j) {
            Z[i + k] = Z[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return Z;
}

template<class T>
vector<int> Zalgorithm(const vector<T> &S) {
    vector<int> Z(S.size());
    Z[0] = (int)S.size();
    int i = 1, j = 0;
    while(i < S.size()) {
        while(i + j < (int)(S.size()) && S[j] == S[i + j]) j++;
        Z[i] = j;

        if(j == 0) {
            i++;
            continue;
        }

        int k = 1;
        while(k < j && k + Z[k] < j) {
            Z[i + k] = Z[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return Z;
}
#line 7 "Test/yosupo-Z-Algorithm.test.cpp"

int main() {

    string S;
    cin >> S;
    vector<int> Z = Zalgorithm(S);
    for(int i = 0; i < (int)(Z.size()); i++) {
        cout << Z[i] << " ";
    }
    cout << endl;

}

Back to top page