Pagini recente » Cod sursa (job #257120) | Cod sursa (job #2709609) | Cod sursa (job #3179593) | Cod sursa (job #2538307) | Cod sursa (job #3253488)
//https://infoarena.ro/problema/strmatch
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
ios_base::sync_with_stdio(false);
//cin.tie(NULL);
string a, b, c, d;
vector <int> sf(2000005, 0);
vector <int> rez;
int i, j, cnt = 0;
fin >> a;
fin >> b;
a = '0' + a;
b = '0' + b;
//cout << a << " " << b << "\n";
for (i = 2, j = 0; i < (int)a.size(); ++i)
{
while (j && (a[j + 1] != a[i]))
{
j = sf[j];
}
//cout << a[i] << " " << a[j + 1] << "\n";
if (a[i] == a[j + 1])
{
++j;
}
sf[i] = j;
//cout << i << " " << j << "\n";
}
/*for (i = 0; i < a.size(); ++i)
{
cout << sf[i] << " ";
}
cout << "\n";*/
for (i = 1, j = 0; i < (int)b.size(); ++i)
{
while ((j != 0) && (a[j + 1] != b[i]))
{
j = sf[j];
}
if (b[i] == a[j + 1])
{
++j;
}
//cout << j << " ";
if (j == ((int)a.size() - 1))
{
++cnt;
if (cnt <= 1000)
{
rez.push_back(i - (int)a.size() + 1);
}
j = sf[j];
}
}
fout << cnt << "\n";
for (auto x : rez)
{
fout << x << " ";
}
return 0;
}