Z-Algorithm
(C++/string/z-algo.hpp)

• View this file on GitHub
• Last update: 2024-02-19 12:47:06+09:00
• Include: #include "C++/string/z-algo.hpp"

Verified with

• test/zalgo.test.cpp

Code

#pragma once

#include <vector>
std::vector<int> zalg(const std::string &s) {
    const int n = s.size();
    int j = 0;
    std::vector<int> pre(n);
    for(int i = 1; i < n; ++i) {
        if(i + pre[i - j] < j + pre[j]) pre[i] = pre[i - j];
        else {
            int k = std::max(0, j + pre[j] - i);
            while(i + k < n && s[k] == s[i + k]) ++k;
            pre[i] = k;
            j = i;
        }
    }
    pre.front() = n;
    return pre;
}

/**
 * @brief Z-Algorithm
 */

#line 2 "C++/string/z-algo.hpp"

#include <vector>
std::vector<int> zalg(const std::string &s) {
    const int n = s.size();
    int j = 0;
    std::vector<int> pre(n);
    for(int i = 1; i < n; ++i) {
        if(i + pre[i - j] < j + pre[j]) pre[i] = pre[i - j];
        else {
            int k = std::max(0, j + pre[j] - i);
            while(i + k < n && s[k] == s[i + k]) ++k;
            pre[i] = k;
            j = i;
        }
    }
    pre.front() = n;
    return pre;
}

/**
 * @brief Z-Algorithm
 */

Back to top page