Pagini recente » Cod sursa (job #2291671) | Cod sursa (job #21010) | Cod sursa (job #1295338) | Cod sursa (job #542229) | Cod sursa (job #2096281)
#include <bits/stdc++.h>
#define LMAX 2000000
#define BAZA 75
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int nrap,val,rhash,lgt,lgp,putere=1;
char A[LMAX+1],B[LMAX+1];
vector <int> V;
void Rabin_Karp(char T[], char P[])
{
lgt=strlen(T);
lgp=strlen(P);
for(int i=1; i<=lgp-1; i++)
{
putere*=BAZA;
putere%=MOD1;
}
for(int i=0; i<lgp; i++)
val=(val*BAZA%MOD1%MOD2+(P[i]-'0'))%MOD1%MOD2;
///fo<<val<<"\n";
for(int i=0; i<lgp; i++)
rhash=(rhash*BAZA%MOD1/*%MOD2*/+(T[i]-'0'))%MOD1/*%MOD2*/;
///fo<<rhash<<"\n";
if(rhash==val)
{
nrap++;
V.push_back(0);
}
for(int i=lgp; i<lgt; i++)
{
rhash=(((rhash-putere*(T[i-lgp]-'0'))%MOD1+MOD1)*BAZA+(T[i]-'0'))%MOD1;
///rhash=(((rhash-putere*(T[i-lgp]-'0'))%MOD2+MOD2)*BAZA+(T[i]-'0'))%MOD2;
if(rhash==val && nrap<1000)
{
nrap++;
V.push_back(i-lgp+1);
}
///fo<<rhash<<"\n";
}
}
void afisare(void)
{
fo<<nrap<<"\n";
for(int i=0; i<V.size(); i++)
fo<<V[i]<<" ";
}
int main()
{
fi>>A;
fi>>B;
Rabin_Karp(B,A);
afisare();
fi.close();
fo.close();
return 0;
}