Pagini recente » Cod sursa (job #926239) | Cod sursa (job #2497465) | Cod sursa (job #2555359) | Cod sursa (job #1489892) | Cod sursa (job #2988020)
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int NMAX = 2000000;
int z[2 * NMAX + 1];
vector <int> sol;
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;
}
}
}
}
for (i = a.size(); i < s.size(); i++)
if (z[i] >= a.size())
{
sol.push_back(i - a.size());
}
cout << sol.size() << "\n";
int v = min((int)sol.size(), 1000);
for (i = 0; i < v; i++)
cout << sol[i] << " ";
}