Pagini recente » Cod sursa (job #2304722) | Cod sursa (job #773588) | Cod sursa (job #1938450) | Cod sursa (job #2983522) | Cod sursa (job #3214254)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A , B;
int z[2000001] , ans;
vector <int> v;
void ZFunction (string &A , string &B)
{
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 >> A >> B;
ZFunction(B , A);
}