Pagini recente » Cod sursa (job #1330655) | Cod sursa (job #2599259) | Cod sursa (job #1419612) | Cod sursa (job #2155525) | Cod sursa (job #2312825)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5,MOD=1e5+21,BAZA=75;
char c[NMAX],t[NMAX];
vector <int> v;
int putere=1,lc,lt,valCuv,valHash;
void citire()
{
fin>>c>>t;
}
void RabinKarp()
{
lc=strlen(c);
lt=strlen(t);
for(int i=1; i<=lc-1 ; i++)
putere=putere*BAZA%MOD;
valCuv=0;
for(int i=0; i<lc; i++)
{
valCuv=(valCuv*BAZA)%MOD+(c[i]-'0')%MOD;
valCuv=valCuv%MOD;
}
valHash=0;
for(int i=0; i<lc; i++)
{
valHash=(valHash*BAZA)%MOD+(t[i]-'0')%MOD;
valHash=valHash%MOD;
}
if(valCuv==valHash)
v.push_back(0);
for(int i=lc; i<lt; i++)
{
valHash=(((valHash-putere*(t[i-lc]-'0'))%MOD+MOD)*BAZA+(t[i]-'0'))%MOD;
if(valHash==valCuv)
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;
}