Pagini recente » Istoria paginii utilizator/ciprian_andrei | Diferente pentru concursuri intre reviziile 182 si 74 | Cod sursa (job #1667853) | Cod sursa (job #3313241) | Cod sursa (job #3333032)
#include "bits/stdc++.h"
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
long long mod,s[20002],poz[1002],pp[20002];
char a[20002],b[20002];
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;
}