Pagini recente » Cod sursa (job #921185) | Cod sursa (job #3355641) | Cod sursa (job #2209682) | Cod sursa (job #3353591) | Cod sursa (job #3349342)
#include <fstream>
#include <cassert>
#include <vector>
#define ll long long
using namespace std;
const int NMAX = 2e6;
int pozitie[NMAX + 1];
int vecin[NMAX + 1];
vector <int> sol;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int i;
string a, b;
cin >> a >> b;
a = "!" + a;
b = "!" + b;
vecin[1] = 0;
vecin[0] = -1;
for (i = 2; i < a.size(); i++)
{
int ax = vecin[i - 1];
while (ax > -1 and a[ax + 1] != a[i])
ax = vecin[ax];
vecin[i] = ax + 1;
}
/*for (i = 1; i < a.size(); i++)
cout << vecin[i] << " ";
cout << "\n";*/
pozitie[0] = 0;
for (i = 1; i < b.size(); i++)
{
int ax = pozitie[i - 1];
if (ax == a.size())
ax = vecin[ax];
while (ax > -1 and a[ax + 1] != b[i])
ax = vecin[ax];
pozitie[i] = ax + 1;
}
/*for (i = 1; i < b.size(); i++)
cout << pozitie[i] << " ";
cout << "\n";*/
for (i = 1; i < b.size(); i++)
if (pozitie[i] == a.size() - 1)
sol.push_back(i - 1 - pozitie[i] + 1);
cout << sol.size() << "\n";
sol.resize(min((int)sol.size(), 1000));
for (int x : sol)
cout << x << " ";
}