Pagini recente » Cod sursa (job #1830147) | Cod sursa (job #1557319) | Cod sursa (job #219934) | Cod sursa (job #934982) | Cod sursa (job #3277787)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int BAZA1=67;
const int BAZA2=73;
const int MOD1=999983;
const int MOD2=999979;
int rasp[2000005];
int hash1(int x)
{
int galeata=0;
int put=1;
while(x!=0)
{
galeata=(galeata+((x%10)*put)%MOD1)%MOD1;
x/=10;
put*=BAZA1;
}
return galeata;
}
int hash2(int x)
{
int galeata=0;
int put=1;
while(x!=0)
{
galeata=(galeata+((x%10)*put)%MOD2)%MOD2;
x/=10;
put*=BAZA2;
}
return galeata;
}
int main()
{
string A,B;
cin>>A>>B;
int n=A.size(), m=B.size();
int codA=0;
int a=0;
for(int i=n-1;i>=0;i--)
a=a*10+(A[i]-'0');
codA=hash2(hash1(a));
int nrrasp=0;
int codB=0;
int nrB=0;
for(int i=n-1;i>=0;i--)
nrB=nrB*10+(B[i]-'0');
codB=hash2(hash1(nrB));
if(codB==codA)
{
nrrasp++;
rasp[nrrasp]=0;
}
int p=pow(10, n);
for(int i=n;i<m;i++)
{
nrB=nrB*10+(B[i]-'0');
nrB=nrB%10;
codB=hash2(hash1(nrB));
if(codB==codA)
{
nrrasp++;
rasp[nrrasp]=i-(n-1);
}
}
cout<<nrrasp<<'\n';
for(int i=1;i<=min(nrrasp, 1000);i++)
cout<<rasp[nrrasp]<<" ";
return 0;
}