Pagini recente » Cod sursa (job #1808440) | Cod sursa (job #1298739) | Cod sursa (job #2952976) | Cod sursa (job #1962136) | Cod sursa (job #2196957)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define NMAX 20000000
#define MOD 50007
char A[NMAX],B[NMAX];
int NA, NB, hashA=0, hashB=0,P=255, PA=1, SOL[NMAX], k=0;
int main()
{
cin>>A;
cin>>B;
NA=strlen(A);
NB=strlen(B);
if(NA>NB){
cout<<0;
return 0;
}
int xd=A[0];
for(int i=0;i<NA;i++){
hashA= (hashA*P + A[i])%MOD;
if(i!=0)
PA=(PA*P)%MOD;
}
for(int i=0;i<NA;i++){
hashB= (hashB*P + B[i])%MOD;
}
if(hashA==hashB)
SOL[++k]=0;
for(int i=NA;i<NB;i++){
hashB= (((hashB-(B[i-NA]*PA)%MOD)+MOD)*P + B[i])%MOD;
if(hashA==hashB)
SOL[++k]=i-NA+1;
}
cout<<k<<endl;
for(int i=1;i<=k&&i<=1000;i++)
cout<<SOL[i]<<' ';
}