Pagini recente » Cod sursa (job #2118788) | Cod sursa (job #3261635) | Cod sursa (job #820075) | Cod sursa (job #28609) | Cod sursa (job #2772633)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define NMAX 20000000
char A[NMAX],B[NMAX];
int NA, NB, hashA=0, hashB=0,P=33, 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;
}
for(int i=0;i<NA;i++){
hashA= hashA*P + A[i];
if(i!=0)
PA=PA*P;
}
for(int i=0;i<NA;i++){
hashB= hashB*P + B[i];
}
if(hashA==hashB)
SOL[++k]=0;
for(int i=NA;i<NB;i++){
hashB= (hashB-(B[i-NA]*PA))*P + B[i];
if(hashA==hashB)
SOL[++k]=i-NA+1;
}
cout<<k<<endl;
for(int i=1;i<=k&&i<=1000;i++)
cout<<SOL[i]<<' ';
}