Pagini recente » Statistici Octav Teo (toptoptop) | Rating Zanfir Raluca (Ralucaa_1977) | Cod sursa (job #200729) | Cod sursa (job #212743) | Cod sursa (job #2196952)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define NMAX 20000000
#define MOD 10007
char A[NMAX],B[NMAX];
int NA, NB, hashA=0, hashB=0,P=73, 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]<<' ';
}