Pagini recente » Cod sursa (job #2883553) | Cod sursa (job #702114) | Cod sursa (job #171868) | Cod sursa (job #1122918) | Cod sursa (job #1076192)
#include<fstream>
#include<cstring>
#include<iostream>
#define mod1 100007
#define mod2 100021
using namespace std;
char a[20000002],b[20000002];
long n,m,i,v[1001],nr;
long ha1,ha2,hb1,hb2;
long h1=1,h2=1;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a; f>>b;
m=strlen(a);
n=strlen(b);
for(i=0;i<m;i++)
{
ha1=(ha1*10+a[i])%mod1;
hb1=(hb1*10+b[i])%mod1;
ha2=(ha2*10+a[i])%mod2;
hb2=(hb2*10+b[i])%mod2;
if(i)
{h1=(h1*10)%mod1;
h2=(h2*10)%mod2;}
}
for(i=0;i<=n-m;i++)
{
if(ha1==hb1&&ha2==hb2)
{
nr++;
if(nr<=1000) v[nr]=i;
}
hb1=(10*(hb1-(b[i]*h1)%mod1)+b[i+m])%mod1;
hb2=(10*(hb2-(b[i]*h2)%mod2)+b[i+m])%mod2;
}
g<<nr<<'\n';
for(i=1;i<=nr && i<=1000;i++)
g<<v[i]<<" ";
}