lib/z_algorithm.hpp

• View this file on GitHub
• Last update: 2020-05-15 17:57:27+09:00
• Include: #include "lib/z_algorithm.hpp"

Verified with

• test/z_algorithm.yosupo.zalgorithm.test.cpp

Code

#ifndef CPLIB_CLIB_Z_ALGORITHM_H_
#define CPLIB_CLIB_Z_ALGORITHM_H_

#include <vector>
#include <string>
#include <algorithm>

std::vector<int> z_algorithm(const std::string &s) {
    int n = s.size();
    std::vector<int> ret(n);
    ret[0] = n;
    int begin = 1, len = 0;
    while (begin < n) {
        while (begin + len < n && s[len] == s[begin + len]) len++;
        ret[begin] = len;
        int t = 1;
        while (t < len && t + ret[t] < len) {
            ret[begin + t] = ret[t];
            t++;
        }
        begin += t; len = std::max(0, len - t);
    }
    return ret;
}

#endif  // CPLIB_CLIB_Z_ALGORITHM_H_

#line 1 "lib/z_algorithm.hpp"



#include <vector>
#include <string>
#include <algorithm>

std::vector<int> z_algorithm(const std::string &s) {
    int n = s.size();
    std::vector<int> ret(n);
    ret[0] = n;
    int begin = 1, len = 0;
    while (begin < n) {
        while (begin + len < n && s[len] == s[begin + len]) len++;
        ret[begin] = len;
        int t = 1;
        while (t < len && t + ret[t] < len) {
            ret[begin + t] = ret[t];
            t++;
        }
        begin += t; len = std::max(0, len - t);
    }
    return ret;
}

Back to top page