Pagini recente » Cod sursa (job #2892698) | Cod sursa (job #1825645) | Cod sursa (job #1556314) | Cod sursa (job #944708) | Cod sursa (job #2988021)
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int NMAX = 2000000;
int z[2 * NMAX + 1];
int sol[1000 + 1];
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int i;
string a, b;
cin >> a >> b;
string s = a + b;
int l, r;
l = r = 0;
z[0] = s.size();
for (i = 1; i < s.size(); i++)
{
if (i > r)
{
for (int j = i, ind = 0; j < s.size() and s[j] == s[ind]; j++, ind++)
z[i]++;
if (r < i + z[i] - 1)
{
r = i + z[i] - 1;
l = i;
}
}
else
{
int beta = r - i + 1;
int alfa = r - l + 1;
int i_prim = alfa - beta;
if (z[i_prim] != beta)
z[i] = min(z[i_prim], beta);
else
{
for (int j = i, ind = 0; j < s.size() and s[j] == s[ind]; j++, ind++)
z[i]++;
if (r < i + z[i] - 1)
{
r = i + z[i] - 1;
l = i;
}
}
}
}
int nr = 0;
for (i = a.size(); i < s.size(); i++)
if (z[i] >= a.size())
{
nr++;
if (nr <= 1000)
sol[nr] = i - a.size();
}
cout << nr << "\n";
nr = min(nr, 1000);
for (i = 1; i <= nr; i++)
cout << sol[i] << " ";
}