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