Pagini recente » Cod sursa (job #1259535) | Cod sursa (job #1308868) | Cod sursa (job #2256233) | Cod sursa (job #1253820) | Cod sursa (job #2540085)
#include <fstream>
#include <cstring>
#define NMAX 2000010
#define MOD1 100007
#define MOD2 100021
#define P 73
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[NMAX], B[NMAX];
int nA, nB;
bool mark[NMAX];
long long hashA1,hashA2,hashB1,hashB2, P1, P2;
int main()
{
cin>>A;
cin>>B;
nA=strlen(A);
nB=strlen(B);
hashA1=hashA2=0;
P1=P2=1;
for(int i=0; i<nA; ++i)
{
hashA1=(hashA1*P+A[i])%MOD1;
hashA2=(hashA2*P+A[i])%MOD2;
if(i<nA-1)
{
P1=P1*P, P1%=MOD1;
P2=P2*P, P2%=MOD2;
}
}
hashB1=hashB2=0;
for(int i=0; i<nA; ++i)
{
hashB1=(hashB1*P+B[i])%MOD1;
hashB2=(hashB2*P+B[i])%MOD2;
}
mark[0]=(hashA1==hashB1 && hashA2==hashB2);
int nr=0;
nr+=mark[0];
for(int j=nA; j<nB; ++j)
{
hashB1=((hashB1+MOD1-(B[j-nA]*P1)%MOD1)%MOD1)*P+B[j];
hashB1%=MOD1;
hashB2=((hashB2+MOD2-(B[j-nA]*P2)%MOD2)%MOD2)*P+B[j];
hashB2%=MOD2;
mark[j-nA+1]=(hashA1==hashB1 && hashA2==hashB2);
nr+=mark[j-nA+1];
}
cout<<nr<<'\n';
for(int i=0; i<nB && nr>0; ++i)
if(mark[i])
cout<<i<<' ', --nr;
return 0;
}