Pagini recente » Cod sursa (job #2985442) | Borderou de evaluare (job #1261725) | Borderou de evaluare (job #2332344) | Borderou de evaluare (job #2970147) | Cod sursa (job #3252704)
//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 d[4000005];
int main()
{
ios_base::sync_with_stdio(false);
//cin.tie(NULL);
string a, b, c;
int i, j, k, ii, jj, kk, cnt = 0;
vector <int> rez;
fin >> a;
fin >> b;
c = a + "#" + b;
//cout << (int)c.size() << "\n\n";
i = 1;
d[0] = (int)a.size();
while (c[i] != '#')
{
j = i;
k = 0;
while (c[j] == c[k])
{
++d[i];
++j;
++k;
}
++i;
}
++i;
while (i < (int)c.size())
{
//vad cate sunt egale
j = i;
k = 0;
while ((j < (int)c.size()) && (c[j] == c[k]))
{
++d[i];
++j;
++k;
}
//adaug la rezultat daca e cazul
if (d[i] == d[0])
{
++cnt;
if (cnt <= 1000)
{
rez.push_back(i - (int)a.size() - 1);
}
}
ii = i;
//ma duc pe cele egale si le pun pe nr defintie
for (j = ii + 1, k = 1; ((j < (int)c.size()) && (k < d[ii])); ++j, ++k)
{
d[j] = min(d[k], ((int)c.size() - ii));
if (d[j])
{
//incerc sa le continui
jj = j + 1;
kk = d[j];
while ((jj < (int)c.size()) && (c[jj] == c[kk]))
{
++d[j];
++jj;
++kk;
}
}
//adaug la rezultat daca e cazul
if (d[j] == d[0])
{
++cnt;
if (cnt <= 1000)
{
rez.push_back(j - (int)a.size() - 1);
}
}
++i;
}
++i;
}
/*for (i = 0; i < c.size(); ++i)
{
cout << d[i] << " ";
}*/
fout << cnt << "\n";
for (auto x : rez)
{
fout << x << " ";
}
return 0;
}