Pagini recente » Cod sursa (job #1645213) | Cod sursa (job #2788712) | Cod sursa (job #2727548) | Cod sursa (job #870713) | Cod sursa (job #2281877)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int N = 2000000 + 5;
string pat, s;
int n, m;
int ps[N];
vector<int>id;
inline void build_ps()
{
ps[0] = 1;
int i = 1;
int cur = 0;
while (i < m)
{
if (pat[i] == pat[cur])
{
cur++;
ps[i] = cur;
i++;
}
else
{
if (cur == 0)
{
i++;
}
else
{
cur = ps[cur - 1];
}
}
}
}
inline void kmp()
{
int i = 0;
int j = 0;
while (i < n)
{
if (s[i] == pat[j])
{
i++;
j++;
}
if (j == m)
{
id.push_back (i - m);
j = ps[j - 1];
}
else
{
if (i < n && s[i] != pat[j])
{
if (j == 0)
{
i++;
}
else
{
j = ps[j - 1];
}
}
}
}
}
int main()
{
fin >> pat >> s;
m = pat.size();
n = s.size();
build_ps();
kmp();
fout << id.size() << "\n";
while (id.size() > 1000)
{
id.pop_back();
}
for (auto &x : id)
{
fout << x << " ";
}
fout << "\n";
return 0;
}