Pagini recente » Cod sursa (job #42170) | Istoria paginii runda/oji_bv_2022/clasament | Cod sursa (job #2441748) | Cod sursa (job #1204417) | Cod sursa (job #2752718)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int p=73;
const int MOD1=666013;
const int MOD2=100007;
const int MAXN=2000001;
string a,b;
int p1,p2,reza1,reza2,rez1,rez2,na,nb,nr,i;
bool identitate [MAXN];
int main()
{
fin >>a>>b;
if (na>nb)
{
fout <<0;
return 0;
}
na=a.size ();
nb=b.size ();
reza1=0;
reza2=0;
p1=1;
p2=1;
for (i=0;i<na;++i)
{
reza1=(reza1*p+a[i])%MOD1;
reza2=(reza2*p+a[i])%MOD2;
if (i>0)
{
p1=(p1*p)%MOD1;
p2=(p2*p)%MOD2;
}
}
rez1=0;
rez2=0;
nr=0;
for (i=0;i<na;++i)
{
rez1=(rez1*p+b[i])%MOD1;
rez2=(rez2*p+b[i])%MOD2;
}
if (rez1==reza1 and rez2==reza2)
{
identitate[0]++;
nr++;
}
for (i=na;i<nb;++i)
{
rez1=((rez1-(b[i-na]*p1)%MOD1)*p+b[i])%MOD1;
rez2=((rez2-(b[i-na]*p2)%MOD2)*p+b[i])%MOD2;
if (rez1==reza1 and rez2==reza2)
{
identitate[i-na+1]=1;
nr++;
}
}
fout <<nr<<'\n';
nr=0;
for (i=0;i<nb and nr<1000;++i)
{
if (identitate[i]==1)
{
fout <<i<<' ';
nr++;
}
}
fin.close ();
fout.close ();
return 0;
}