Pagini recente » Cod sursa (job #54333) | Cod sursa (job #60047) | Cod sursa (job #3142468) | Cod sursa (job #2148172) | Cod sursa (job #2372951)
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=2*1000*1000+5;
string a,b;
int z[2*nmax];
int occ[1005];
int ans,i,r,c,n;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a>>b;
n=a.size();
a+=b;r=c=-1;
for(i=1;i<a.size();i++)
{
if(i<r) z[i]=min(r-i,z[i-c]);
if(z[i]<0) z[i]=0;
while(a[i+z[i]]==a[z[i]]) z[i]++;
if(i+z[i]>r) c=i,r=i+z[i];
if(i>=n&&z[i]>=n)
{
ans++;
if(ans<=1000)
occ[ans]=i-n;
}
z[i]--;
}
g<<ans<<'\n';
for(i=1;i<=min(ans,1000);i++)
g<<occ[i]<<' ';
return 0;
}