Pagini recente » Cod sursa (job #1702459) | Cod sursa (job #1205338) | Cod sursa (job #514252) | Cod sursa (job #1412356) | Cod sursa (job #2923133)
#include <fstream>
#include <vector>
#include <cstring>
const int B=127;
const int MOD=666013;
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005], b[2000005];
vector <int> v;
int lga, lgb, pt, coda, codb, i;
int h(char *, int, int);
int next_hash(char *, int, int, int, int);
int rid_pt(int, int);
int main()
{
fin>>a>>b;
lga=strlen(a); lgb=strlen(b);
if(lga>lgb)
{
fout<<0<<'\n';
return 0;
}
coda=h(a, 0, lga-1);
codb=h(b, 0, lga-1);
if(coda==codb && strncmp(a, b, lga)==0)
{
v.push_back(1);
}
pt=rid_pt(B, lga-1);
for(i=lga; i<lgb; i++)
{
codb=next_hash(b, i, i-lga, codb, pt);
if(codb==coda && strncmp(a, b+(i-lga+1), lga)==0)
{
v.push_back(i-lga+1);
}
}
fout<<v.size()<<'\n';
for(auto i:v) fout<<i<<' ';
fout<<'\n';
}
int h(char *a, int start, int final)
{
int i, hs=0;
for(i=start; i<=final; i++)
{
hs=((hs*B)%MOD+int(a[i]))%MOD;
}
return hs;
}
int rid_pt(int nr, int pt)
{
int p=1;
while(pt--)
{
p=(p*nr)%MOD;
}
return p;
}
int next_hash(char *s, int poz, int pozf, int cod, int pt)
{
int elim = ( cod - ( int(s[pozf]) * pt ) %MOD + MOD ) %MOD;
cod=(elim * B + s[poz])%MOD;
return cod;
}