Pagini recente » Cod sursa (job #2006881) | Cod sursa (job #1420021) | Cod sursa (job #1883592) | Cod sursa (job #1848643) | Cod sursa (job #2684868)
//Rabin-Karp
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000002
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int MOD1=1000007, MOD2=1000011;
char a[NMAX], b[NMAX];
int afis[NMAX];
int putere(int x, int e, int mod)
{
if(e==0) return 1;
if(e%2==0) return putere(1LL*x*x%mod, e/2, mod);
return x*putere(1LL*x*x%mod, e/2, mod)%mod;
}
int main()
{
int n, m, i, pow1, pow2, ha1=0, ha2=0, hb1=0, hb2=0, nr_afis=0;
const int bz=123;
fin.getline(a, NMAX); n=strlen(a);
fin.getline(b, NMAX); m=strlen(b);
for(i=0; i<n; i++)
{
hb1=(hb1*bz+b[i])%MOD1;
hb2=(hb2*bz+b[i])%MOD2;
ha1=(ha1*bz+a[i])%MOD1;
ha2=(ha2*bz+a[i])%MOD2;
}
pow1=putere(bz, n-1, MOD1);
pow2=putere(bz, n-1, MOD2);
//sau
if(ha1==hb1 && ha2==hb2) afis[++nr_afis]=0; //incepand cu pozitia 0
for(i=n; i<m; i++)
{
hb1=((hb1%MOD1-1LL*b[i-n] * pow1 %MOD1+MOD1)%MOD1*bz+b[i])%MOD1;
hb2=((hb2%MOD2-1LL*b[i-n] * pow2 %MOD2+MOD2)%MOD2*bz+b[i])%MOD2;
//sau h=h % pow * pow+b[i];
if(ha1==hb1 && ha2==hb2) afis[++nr_afis]=i-n+1;
}
fout<<nr_afis<<"\n";
for(i=1; i<=nr_afis; i++) fout<<afis[i]<<' ';
}