Pagini recente » Cod sursa (job #2667410) | Cod sursa (job #2566630) | Cod sursa (job #1006269) | Cod sursa (job #2288597) | Cod sursa (job #2312808)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5,MOD=1e5+7,BAZA=260;
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-((t[i-lc]-'\0')*putere)%MOD;
valHash=(valHash+MOD)%MOD;
valHash=(valHash*BAZA)%MOD;
valHash=(valHash+(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;
}