Pagini recente » Cod sursa (job #658419) | Cod sursa (job #1315255) | Cod sursa (job #2919848) | Cod sursa (job #1094969) | 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;
}