Zalgorithm
(String/Zalgorithm.hpp)

• View this file on GitHub
• Last update: 2023-07-12 13:20:16+00:00
• Include: #include "String/Zalgorithm.hpp"

Zalgorithm

(1) vector<int> Zalgorithm(string S)
(2) vector<int> Zalgorithm(vector<T> S)

$S$ の長さを $N$ として, 長さ $N$ の配列を返す. $i$番目の要素はs[0..N)とs[i..N)の最長共通接頭辞.

計算量

• $O(N)$

Verified with

• Test/yosupo-Z-Algorithm.test.cpp

Code

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 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;
}

Back to top page