library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kazunetakahashi/library

:heavy_check_mark: Strings/KMP.cpp

Back to top page

Verified with

Code

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// ----- MP algorithm -----

template <typename Type = string>
class MP
{
  int N;
  Type S;
  vector<int> A;

public:
  MP() {}
  MP(Type const &S) : N(S.size()), S{S}, A(N + 1, -1)
  {
    int j{-1};
    for (auto i{0}; i < N; i++)
    {
      while (j != -1 && S[j] != S[i])
      {
        j = A[j];
      }
      ++j;
      A[i + 1] = j;
    }
  }

  int operator[](int i) const { return A[i]; }

  int period(int i) const
  { // The period of S[0, i).
    auto tmp{i - A[i]};
    if (i % tmp == 0)
    {
      return tmp;
    }
    return i;
  }

  vector<int> place(Type const &T) const
  {
    vector<int> res;
    int j{0};
    for (auto i{size_t{0}}; i < T.size(); i++)
    {
      while (j != -1 && S[j] != T[i])
      {
        j = A[j];
      }
      ++j;
      if (j == N)
      {
        res.push_back(i - j + 1);
        j = A[j];
      }
    }
    return res;
  }

  vector<bool> table(Type const &T) const
  {
    vector<bool> res(T.size(), false);
    for (auto e : place(T))
    {
      res[e] = true;
    }
    return res;
  }
};

#line 1 "Strings/KMP.cpp"
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// ----- MP algorithm -----

template <typename Type = string>
class MP
{
  int N;
  Type S;
  vector<int> A;

public:
  MP() {}
  MP(Type const &S) : N(S.size()), S{S}, A(N + 1, -1)
  {
    int j{-1};
    for (auto i{0}; i < N; i++)
    {
      while (j != -1 && S[j] != S[i])
      {
        j = A[j];
      }
      ++j;
      A[i + 1] = j;
    }
  }

  int operator[](int i) const { return A[i]; }

  int period(int i) const
  { // The period of S[0, i).
    auto tmp{i - A[i]};
    if (i % tmp == 0)
    {
      return tmp;
    }
    return i;
  }

  vector<int> place(Type const &T) const
  {
    vector<int> res;
    int j{0};
    for (auto i{size_t{0}}; i < T.size(); i++)
    {
      while (j != -1 && S[j] != T[i])
      {
        j = A[j];
      }
      ++j;
      if (j == N)
      {
        res.push_back(i - j + 1);
        j = A[j];
      }
    }
    return res;
  }

  vector<bool> table(Type const &T) const
  {
    vector<bool> res(T.size(), false);
    for (auto e : place(T))
    {
      res[e] = true;
    }
    return res;
  }
};

Back to top page