Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/ruxi1204 | Monitorul de evaluare | Statistici iulian radu (don_iuliano) | Cod sursa (job #2695890)
#include <bits/stdc++.h>
#define MOD1 100007
#define MOD2 100021
#define p 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000010],b[2000010];
int poz,i,pozitiea,pozitieb,pozitie,l1,l2,numar,p1,p2,hasha1,hashb1,hasha2,hashb2;
int v[1010];
int main()
{
fin>>a>>b;
l1=strlen(a);
l2=strlen(b);
if(l1>l2)
{
fout<<0;
return 0;
}
p1=p2=1;
for(i=0;i<l1;i++)
{
hasha1=(hasha1*p%MOD1+a[i]%MOD1)%MOD1;
hasha2=(hasha2*p%MOD2+a[i]%MOD2)%MOD2;
hashb1=(hashb1*p%MOD1+b[i]%MOD1)%MOD1;
hashb2=(hashb2*p%MOD2+b[i]%MOD2)%MOD2;
if(i>0)
{
p1=(p1*p)%MOD1;
p2=(p2*p)%MOD2;
}
}
if(hasha1==hashb1 && hasha2==hashb2)
v[++numar]=0;
for(i=l1;i<l2;i++)
{
hashb1=(((hashb1+MOD1-(b[i-l1]*p1)%MOD1)*p%MOD1)+b[i])%MOD1;
hashb2=(((hashb2+MOD2-(b[i-l1]*p2)%MOD2)*p%MOD2)+b[i])%MOD2;
if(hasha1==hashb1 && hasha2==hashb2)
{
numar++;
if(numar<=1000)
v[numar]=i-l1+1;
}
}
fout<<numar<<'\n';
numar=min(numar,1000);
for(i=1;i<=numar;i++)
fout<<v[i]<<" ";
return 0;
}