Pagini recente » Cod sursa (job #2660958) | Cod sursa (job #2438072) | Cod sursa (job #346003) | Cod sursa (job #2897229) | Cod sursa (job #3253482)
//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;
//cout << a << " " << b << "\n";
for (i = 1, j = 0; i < a.size(); ++i)
{
while (j && (a[j] != a[i]))
{
j = sf[j];
}
//cout << a[i] << " " << a[j + 1] << "\n";
if (a[i] == a[j])
{
++j;
}
sf[i] = j;
//cout << i << " " << j << "\n";
}
/*for (i = 0; i < a.size(); ++i)
{
cout << sf[i] << " ";
}
cout << "\n";*/
for (i = 0, j = 0; i < 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 == (a.size() - 1))
{
++cnt;
if (cnt <= 1000)
{
rez.push_back(i - a.size() + 1);
}
j = sf[j];
}
}
fout << cnt << "\n";
for (auto x : rez)
{
fout << x << " ";
}
return 0;
}