Pagini recente » Cod sursa (job #2544424) | Cod sursa (job #2072195) | Istoria paginii implica-te/arhiva-educationala | Cod sursa (job #1516808) | Cod sursa (job #2790565)
#include <bits/stdc++.h>
#define m1 100007
#define m2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,v1,v2,k1=1,k2=1,x1,x2,i;
char a[2000005],b[2000005];
int r[1005],nr;
int main()
{
fin>>a>>b;
for(i=0;a[i];i++)
{
x1=(x1*123+a[i])%m1;
x2=(x2*123+a[i])%m2;
if(i>0)
{
k1=(k1*123)%m1;
k2=(k2*123)%m2;
}
}
n=i;
for(i=0;b[i];i++)
{
if(i<n)
{
v1=(v1*123+b[i])%m1;
v2=(v2*123+b[i])%m2;
if(i==n-1&&x1==v1&&x2==v2)nr++;
}
else {
v1=((v1-(b[i-n]*k1)%m1+m1)*123+b[i])%m1;
v2=((v2-(b[i-n]*k2)%m2+m2)*123+b[i])%m2;
if(x1==v1&&x2==v2)
{
if(nr<1000)
r[++nr]=i-n+1;
else nr++;
}
}
}
fout<<nr<<'\n';
if(nr>1000)nr=1000;
for(i=1;i<=nr;i++)fout<<r[i]<<' ';
return 0;
}