Pagini recente » Cod sursa (job #3303269) | Cod sursa (job #3336566) | Cod sursa (job #3321281) | Atasamentele paginii gard5 | Cod sursa (job #3333034)
#include "bits/stdc++.h"
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
long long mod,s[2000002],poz[1002],pp[2000002];
char a[2000002],b[2000002];
int main ()
{
long long na,nb,p1,sa,x,nr,sb,c1;
f>>a>>b;
na=strlen(a);nb=strlen(b);
p1=998244353;
mod=1000000007;
if (na>nb) g<<0;
else
{
pp[0]=1;
for (x=1;x<nb;x++)
{
pp[x]=(pp[x-1]*p1)%mod;
}
sa=0;
for (x=0;x<na;x++)
{
sa=((sa*p1)%mod+(a[x]-'0'))%mod;
}
s[0]=b[0]-'0';
for (x=1;x<nb;x++)
{
s[x]=((s[x-1]*p1)%mod+(b[x]-'0'))%mod;
}
nr=0;
for (x=0;x+na-1<nb;x++)
{
if (x>0)
{
sb=(s[x+na-1]-(s[x-1]*pp[na])%mod+mod)%mod;
}
else sb=s[x+na-1];
if (sb==sa) {nr++;if (nr<=1000) poz[nr]=x;}
}
g<<nr<<endl;
c1=1000;
for (x=1;x<=min(nr,c1);x++)
{
g<<poz[x]<<" ";
}
}
f.close ();
g.close ();
return 0;
}