test/library_checker/string/z_algorithm.test.cpp

View this file on GitHub
Last update: 2024-05-04 18:06:16+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

Z Algorithm (lib/string/z_algorithm.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/string/z_algorithm.hpp"

int main(){
    string s; cin >> s;
    vector<int> z = z_algorithm(s);
    int n = s.size();
    for(int i = 0; i < n; i++){
        if(i >= 1) cout << " ";
        cout << z[i];
    }
    cout << endl;
}

#line 1 "test/library_checker/string/z_algorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/string/z_algorithm.hpp"

/**
 * @brief Z Algorithm
 * @docs docs/string/z_algorithm.md
 */

template <typename T>
vector<int> z_algorithm(const T &s) {
    int n = s.size();
    vector<int> res(n, 0);
    for(int i = 1, j = 0; i < n; ++i){
        if(i + res[i - j] < j + res[j]){
            res[i] = res[i - j];
        } else{
            res[i] = max(j + res[j] - i, 0);
            while(i + res[i] < n && s[i + res[i]] == s[res[i]]) ++res[i];
            j = i;
        }
    }
    res[0] = n;
    return res;
}
#line 6 "test/library_checker/string/z_algorithm.test.cpp"

int main(){
    string s; cin >> s;
    vector<int> z = z_algorithm(s);
    int n = s.size();
    for(int i = 0; i < n; i++){
        if(i >= 1) cout << " ";
        cout << z[i];
    }
    cout << endl;
}