test/string/Z_Algorithm.test.cpp

• View this file on GitHub
• Last update: 2023-07-17 14:12:40+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• string/Z_Algorithm.hpp

Code

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

#include "../../string/Z_Algorithm.hpp"


#include <iostream>

#include <vector>


int main() {
    std::string s;
    std::cin >> s;
    auto A = ebi::Z_Algorithm(s);
    std::cout << A[0];
    for (int i = 1; i < s.size(); i++) {
        std::cout << " " << A[i];
    }
    std::cout << '\n';
}

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

#line 2 "string/Z_Algorithm.hpp"

#include <string>

#include <vector>


/*
    reference: https://snuke.hatenablog.com/entry/2014/12/03/214243
*/

namespace ebi {

std::vector<int> Z_Algorithm(const std::string &s) {
    int n = s.size();
    std::vector<int> prefix(n);
    prefix[0] = n;
    int i = 1;
    int j = 0;  // s[0,j], s[i,i+j] がすでに一致していることが保証されている.

    while (i < n) {
        while (i + j < n && s[j] == s[i + j]) ++j;
        prefix[i] = j;
        if (j == 0) {
            ++i;
            continue;
        }
        int k = 1;
        while (i + k < n && k + prefix[k] < j) {
            prefix[i + k] = prefix[k];
            ++k;
        }
        i += k;
        j -= k;
    }
    return prefix;
}

}  // namespace ebi
#line 4 "test/string/Z_Algorithm.test.cpp"

#include <iostream>

#line 7 "test/string/Z_Algorithm.test.cpp"

int main() {
    std::string s;
    std::cin >> s;
    auto A = ebi::Z_Algorithm(s);
    std::cout << A[0];
    for (int i = 1; i < s.size(); i++) {
        std::cout << " " << A[i];
    }
    std::cout << '\n';
}

Back to top page