Pagini recente » Cod sursa (job #2770294) | Cod sursa (job #1196920) | Cod sursa (job #927845) | Cod sursa (job #2116289) | Cod sursa (job #2096286)
#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,val1,val2,rhash1,rhash2,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;
putere%=MOD2;
}
for(int i=0; i<lgp; i++)
{
val1=(val1*BAZA%MOD1%MOD2+(P[i]-'0'))%MOD1%MOD2;
val2=(val2*BAZA%MOD1%MOD2+(P[i]-'0'))%MOD1%MOD2;
}
///fo<<val<<"\n";
for(int i=0; i<lgp; i++)
{
rhash1=(rhash1*BAZA%MOD1/*%MOD2*/+(T[i]-'0'))%MOD1/*%MOD2*/;
rhash2=(rhash2*BAZA%MOD2/*%MOD2*/+(T[i]-'0'))%MOD2/*%MOD2*/;
}
///fo<<rhash<<"\n";
if(rhash1==val1 && rhash2==val2)
{
nrap++;
V.push_back(0);
}
for(int i=lgp; i<lgt; i++)
{
rhash1=(((rhash1-putere*(T[i-lgp]-'0'))%MOD1+MOD1)*BAZA+(T[i]-'0'))%MOD1;
rhash2=(((rhash2-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(rhash1==val1 && rhash2==val2 && 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;
}