Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #798431) | Monitorul de evaluare | Cod sursa (job #820543)
Cod sursa(job #820543)
#include<cstdio>
#include<string.h>
#define mod 666013
#define mod2 100107
using namespace std;
char A[2000001], B[2000001];
int poz[1002];
int main()
{
int s1,s2,s21,s22,n=0,pf,pf2,i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",A,B);
int la,lb;
la=strlen(A);
lb=strlen(B);
s1=0;s2=0;
pf=1;pf2=1;
s21=0;s22=0;
for(i=0;i<la;i++)
{
s1=( s1*75 + (A[i]-'0') )%mod;
s2=( s2*75 + (A[i]-'0') )%mod2;
s21=( s21*75 +(B[i]-'0') )%mod;
s22=( s22*75 + (B[i]-'0') )%mod2;
if(i){
pf=(pf*75)%mod;
pf2=(pf2*75)%mod2;
}
}
if(s21==s1&&s22==s2)
{
n++;
poz[n]=0;
}
for(i=la;i<lb;i++)
{
s21=( ( s21 - ( B [ i - la ] -'0' ) * pf % mod + mod ) * 75 + (B[i]-'0') ) % mod;
s22=( ( s22 - ( B [ i - la ]- '0' ) * pf2 % mod2 + mod2 ) * 75 + (B[i]-'0') ) % mod2;
if( s21==s1 && s22==s2 )
if(n<1000) poz[++n]=i-la+1;
else n++;
}
printf("%d\n",n);
for(i=1;i<=n&&i<=1000;i++)
printf("%d ",poz[i]);
return 0;
}