This documentation is automatically generated by online-judge-tools/verification-helper
#include "../KMP.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
int main()
{
string t, p;
cin >> t >> p;
MP<string> mp{p};
for (auto e : mp.place(t))
{
cout << e << endl;
}
}
#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;
}
};
#line 2 "Strings/tests/KMP_string_search.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
int main()
{
string t, p;
cin >> t >> p;
MP<string> mp{p};
for (auto e : mp.place(t))
{
cout << e << endl;
}
}