Pagini recente » Cod sursa (job #977705) | Cod sursa (job #377091) | Cod sursa (job #138887) | Cod sursa (job #1376024) | Cod sursa (job #3253567)
#include <bits/stdc++.h>
#define MAX 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, t;
int z[2*MAX+5], i, l, n;
vector<int>R;
int main()
{
fin>>s>>t;
t=s+'#'+t;
n=t.size();
z[1]=0;
while (t[z[1]]==t[1+z[1]]) z[1]++;
l=1;
for (i=2; i<n; i++) {
z[i]=max(0, min(z[i-l], l+z[l]-i));
while (t[z[i]]==t[i+z[i]]) z[i]++;
if (i+z[i]>l+z[l]) l=i;
}
for (i=1; i<n; i++) {
if (z[i]==s.size()) R.push_back(i-s.size()-1);
}
fout<<R.size()<<'\n';
for (i=0; i<min(int(R.size()), 1000); i++) {
fout<<R[i]<<' ';
}
return 0;
}