Pagini recente » Cod sursa (job #214007) | Cod sursa (job #2980774) | Cod sursa (job #2356358) | Cod sursa (job #71111) | Cod sursa (job #3252751)
//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");
vector <int> rez;
int d[4000005], kr[4000005], cnt;
void adaugRez(const int& i, const int& asz)//adaug la rezultat daca e cazul
{
if (d[i] == d[0])
{
++cnt;
if (cnt <= 1000)
{
rez.push_back(i - asz - 1);
}
}
}
void verifEgale(const int& ij, const int& ik, const int& i, const string& c)//vad cate sunt egale
{
int j, k;
j = ij;
k = ik;
while ((j < (int)c.size()) &&(c[j] == c[k]))
{
++d[i];
++j;
++k;
}
}
void punSim(int& i, const int& csz, const int& asz, const string& c)//ma duc pe cele egale si le pun pe nr defintie
{
int j, k;
for (j = i + 1, k = 1; ((j < csz) && (k < d[i])); ++j, ++k)
{
d[j] = min(max(0, d[k] - (d[0] - d[i])), (csz - j));
//cout << (d[0] - d[i]) << " ";
/*if(j == 12)
{
cout << d[k] << " " << d[0] << " " << d[i] << "\n";
}*/
//cout << d[j] << "\n";
kr[j] = d[j];
}
}
int main()
{
ios_base::sync_with_stdio(false);
//cin.tie(NULL);
string a, b, c;
int i;
fin >> a;
fin >> b;
c = a + "#" + b;
i = 1;
d[0] = (int)a.size();
while (c[i] != '#')
{
verifEgale(i, 0, i, c);
++i;
}
++i;
while (i < (int)c.size())
{
verifEgale(i + kr[i] , kr[i], i, c);
adaugRez(i, (int)a.size());
punSim(i, (int)c.size(), (int)a.size(), c);
++i;
}
/*for (i = a.size() + 1; i < c.size(); ++i)
{
cout << d[i] << " ";
}*/
fout << cnt << "\n";
for (auto x : rez)
{
fout << x << " ";
}
return 0;
}