Pagini recente » Atasamentele paginii Profil Magnani_Patrick | Atasamentele paginii Profil bogdan_gati | Statistici Stoica Liviu (RamsesTK) | Cod sursa (job #3365871) | Cod sursa (job #3365872)
//Z-function
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
int n,m,l,r,i,j,nr,z[4000005];
string a,b,s;
int main()
{
cin>>a>>b;
n=a.size();
m=b.size();
s=a+'#'+b;
l=0;
r=0;
nr=0;
for(i=1;i<s.size();i++)
{
if(i<=r)
z[i]=min(r-i+1,z[i-l]);
while(i+z[i]<s.size() && s[z[i]]==s[i+z[i]])
z[i]++;
if(i+z[i]-1>r)
{
l=i;
r=i+z[i]-1;
}
if(z[i]>=n)
nr++;
}
cout<<nr<<'\n';
j=0;
for(i=n+1;i<s.size() && j<1000;i++)
{
if(z[i]>=n)
{
cout<<i-n-1<<' ';
j++;
}
}
return 0;
}