test/string/Zalgorithm.test.cpp

• View this file on GitHub
• Last update: 2023-05-30 04:39:19+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• Zalgorithm (lib/50-string/Zalgorithm.cpp)

Code

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

#include <vector>
#include <iostream>
using namespace std;
#include "../../lib/50-string/Zalgorithm.cpp"

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    string S; cin >> S;
    Zalgorithm z(S);
    for(int i=0;i<S.size();++i) cout << z[i] << " ";
    cout << endl;
    return 0;
}

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

#include <vector>
#include <iostream>
using namespace std;
#line 1 "lib/50-string/Zalgorithm.cpp"
/*
 * @title Zalgorithm
 * @docs md/string/Zalgorithm.md
 */
class Zalgorithm{
    vector<int> zarray;
    template<class T> void init(const vector<T>& ar) {
        int N = ar.size();
        for(int i = 1, j = 0; i < N; ++i) {
            if(i + zarray[i - j] < j + zarray[j]) {
                zarray[i] = zarray[i - j];
            } 
            else {
                int k = max(0, j + zarray[j] - i);
                while(i + k < N && ar[k] == ar[i + k]) ++k;
                zarray[j = i] = k;
            }
        }
        zarray[0] = N;
    }
public:
    template<class T> Zalgorithm(const vector<T>& ar) : zarray(ar.size()) {
        init(ar);
    }
    Zalgorithm(const string& s) : zarray(s.size()) {
        vector<char> ar(s.size());
        for(int i=0; i<s.size(); ++i) ar[i]=s[i];
        init(ar);
    }
	inline int operator[](int idx) {
		return zarray[idx];
	}
};
#line 7 "test/string/Zalgorithm.test.cpp"

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    string S; cin >> S;
    Zalgorithm z(S);
    for(int i=0;i<S.size();++i) cout << z[i] << " ";
    cout << endl;
    return 0;
}

Back to top page