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

• View this file on GitHub
• Last update: 2023-05-30 04:23:09+09:00

Verified with

• test/string/Zalgorithm.test.cpp

Code

/*
 * @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 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];
	}
};

Back to top page