Pagini recente » Cod sursa (job #552429) | Cod sursa (job #543590) | Cod sursa (job #2518890) | Cod sursa (job #1809217) | Cod sursa (job #2807594)
#include<fstream>
#include<cstring>
#define mod1 100003
#define mod2 100007
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
long long ha1,ha2,na,nb,h1,h2,v[2000001],k,p1=1,p2=1;
char A[2000001],B[2000001];
int c(char ch)
{
return ch;
}
int main()
{
cin>>A;
cin>>B;
na=strlen(A);
nb=strlen(B);
for(int i=0; i<na; i++)
{
ha1=(ha1*73+c(A[i]))%mod1;
ha2=(ha2*73+c(A[i]))%mod2;
}
for(int i=0; i<na; i++)
{
h1=(h1*73+c(B[i]))%mod1;
h2=(h2*73+c(B[i]))%mod2;
if(i)
{
p1=(p1*73)%mod1;
p2=(p2*73)%mod2;
}
}
//p1/=126;
//p2/=126;
if(h1==ha1 && h2==ha2)
v[++k]=0;
for(int i=na; i<nb; i++)
{
h1=((h1-(c(B[i-na])*p1)%mod1+mod1)*73+c(B[i]))%mod1;
h2=((h2-(c(B[i-na])*p2)%mod2+mod2)*73+c(B[i]))%mod2;
if(ha1==h1 && ha2==h2)
v[++k]=i-na+1;
}
cout<<k<<'\n';
if(k>1000)
k=1000;
for(int i=1; i<=k; i++)
cout<<v[i]<<' ';
}