# library

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

View the Project on GitHub kazunetakahashi/library

# Strings/KMP.cpp

## 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;
}
};