Pagini recente » Cod sursa (job #1819132) | Cod sursa (job #1816505) | Cod sursa (job #280820) | Cod sursa (job #2092497) | Cod sursa (job #2312827)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5,MOD1=1e5+7,MOD2=1e5+21,BAZA=75;
char c[NMAX],t[NMAX];
vector <int> v;
int putere1=1,putere2=1,lc,lt,valCuv1,valCuv2,valHash1,valHash2;
void citire()
{
fin>>c>>t;
}
void RabinKarp()
{
lc=strlen(c);
lt=strlen(t);
for(int i=1; i<=lc-1 ; i++)
{
putere1=putere1*BAZA%MOD1;
putere2=putere2*BAZA%MOD2;
}
valCuv1=valCuv2=0;
for(int i=0; i<lc; i++)
{
valCuv1=(valCuv1*BAZA)%MOD1+(c[i]-'0')%MOD1;
valCuv1=valCuv1%MOD1;
valCuv2=(valCuv2*BAZA)%MOD2+(c[i]-'0')%MOD2;
valCuv2=valCuv2%MOD2;
}
valHash1=valHash2=0;
for(int i=0; i<lc; i++)
{
valHash1=(valHash1*BAZA)%MOD1+(t[i]-'0')%MOD1;
valHash1=valHash1%MOD1;
valHash2=(valHash2*BAZA)%MOD2+(t[i]-'0')%MOD2;
valHash2=valHash2%MOD2;
}
if(valCuv1==valHash1 && valCuv2==valHash2)
v.push_back(0);
for(int i=lc; i<lt; i++)
{
valHash1=(((valHash1-putere1*(t[i-lc]-'0'))%MOD1+MOD1)*BAZA+(t[i]-'0'))%MOD1;
valHash2=(((valHash2-putere2*(t[i-lc]-'0'))%MOD2+MOD2)*BAZA+(t[i]-'0'))%MOD2;
if(valCuv1==valHash1 && valCuv2==valHash2)
v.push_back(i-lc+1);
}
}
void afisare()
{
int q=v.size();
fout<<q<<'\n';
for(int i=0; i<min(q,1000); i++)
fout<<v[i]<<" ";
}
int main()
{
citire();
RabinKarp();
afisare();
return 0;
}