Pagini recente » Cod sursa (job #2962163) | Cod sursa (job #2690902) | Cod sursa (job #682537) | Cod sursa (job #730496) | Cod sursa (job #3214257)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A , B;
int z[4000005] , ans;
vector <int> v;
void ZFunction ()
{
int L = 0 , R = 0;
A = B + "$" + A;
for (int i = 0; i < (int)A.size(); ++i)
{
z[i] = min(R - i , z[i - L]);
while(i + z[i] < A.size() && A[z[i]] == A[i + z[i]])
++z[i];
if(i + z[i] > R)
L = i , R = i + z[i];
}
for (int i = 0; i < A.size(); ++i)
{
ans += (z[i] == B.size());
if(v.size() < 1000 && z[i] == B.size())
v.push_back(i - B.size() - 1);
}
fout << ans << "\n";
for (auto x : v)
fout << x << " ";
}
int main()
{
fin >> B >> A;
ZFunction();
}