KMP法

#pragma once
#include <algorithm>
#include <vector>

/// @brief KMP法
/// @see https://snuke.hatenablog.com/entry/2014/12/01/235807
/// @complexity pattern構築は $O(m)$、長さnの検索は $O(n+m)$
template <class Container>
struct knuth_morris_pratt {
    /// @brief pattern tのfailure tableを構築する
    /// @complexity $O(m)$
    knuth_morris_pratt(const Container &_t) : t(_t), data(_t.size() + 1) {
        data[0] = -1;
        int j = -1;
        for (int i = 0; i < (int)t.size(); ++i) {
            while (j >= 0 && t[i] != t[j]) j = data[j];
            if (i + 1 < (int)t.size() && t[i + 1] == t[++j]) data[i + 1] = data[j];
            else if (i + 1 == (int)t.size() && i + 1 == ++j) data[i + 1] = data[j];
            else data[i + 1] = j;
        }
    }

    /// @brief failure tableのi番目を返す
    /// @complexity $O(1)$
    int operator[](int i) const { return data[i]; }

    /// @brief 検索
    /// @complexity $O(n+m)$
    std::vector<int> search(const Container &s) const {
        int n = s.size(), m = t.size();
        std::vector<int> res(n);
        int i = 0, j = 0;
        while (i + j < n) {
            if (j < m && t[j] == s[i + j]) {
                ++j;
                res[i + j - 1] = j;
                continue;
            }
            i += j - data[j];
            j = std::max(data[j], 0);
        }
        return res;
    }

  private:
    Container t;
    std::vector<int> data;
};

bundled

#line 2 "lib/string/kmp.hpp"
#include <algorithm>
#include <vector>

/// @brief KMP法
/// @see https://snuke.hatenablog.com/entry/2014/12/01/235807
/// @complexity pattern構築は $O(m)$、長さnの検索は $O(n+m)$
template <class Container>
struct knuth_morris_pratt {
    /// @brief pattern tのfailure tableを構築する
    /// @complexity $O(m)$
    knuth_morris_pratt(const Container &_t) : t(_t), data(_t.size() + 1) {
        data[0] = -1;
        int j = -1;
        for (int i = 0; i < (int)t.size(); ++i) {
            while (j >= 0 && t[i] != t[j]) j = data[j];
            if (i + 1 < (int)t.size() && t[i + 1] == t[++j]) data[i + 1] = data[j];
            else if (i + 1 == (int)t.size() && i + 1 == ++j) data[i + 1] = data[j];
            else data[i + 1] = j;
        }
    }

    /// @brief failure tableのi番目を返す
    /// @complexity $O(1)$
    int operator[](int i) const { return data[i]; }

    /// @brief 検索
    /// @complexity $O(n+m)$
    std::vector<int> search(const Container &s) const {
        int n = s.size(), m = t.size();
        std::vector<int> res(n);
        int i = 0, j = 0;
        while (i + j < n) {
            if (j < m && t[j] == s[i + j]) {
                ++j;
                res[i + j - 1] = j;
                continue;
            }
            i += j - data[j];
            j = std::max(data[j], 0);
        }
        return res;
    }

  private:
    Container t;
    std::vector<int> data;
};