Pagini recente » Cod sursa (job #150925) | Cod sursa (job #844654) | Cod sursa (job #2788301) | Cod sursa (job #1924451) | Cod sursa (job #2449198)
/// Z
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int dim = 4000005;
string s1,s2;
vector <int> omg;
int l,r,z[dim];
int main()
{
in >> s1 >> s2;
if (s1.length() > s2.length())
{
out << "0";
return 0;
}
s2 = s1 + "$" + s2;
int l = 0,r = 0;
int n = s2.length();
for (int i=1; i<n; i++)
{
if (i > r)
{
l = i;
r = i;
while (r < n && s2[r] == s2[r-l])
{
r++;
}
z[i] = r-l;
r--;
}
else
{
if (z[i-l] < r-i+1)
{
z[i] = z[i-l];
}
else
{
l = i;
while (r < n && s2[r] == s2[r-l])
{
r++;
}
z[i] = r-l;
r--;
}
}
}
int cnt = 0;
for (int i=0; i<n; i++)
{
if (z[i] == s1.length())
{
cnt++;
omg.push_back(i);
}
}
out << cnt << "\n";
if (omg.size() <= 1000)
{
for (int i=0; i<omg.size(); i++)
{
out << omg[i] - s1.length() - 1 << " ";
}
}
else
{
for (int i=0; i<1000; i++)
{
out << omg[i] - s1.length() - 1 << " ";
}
}
return 0;
}