Pagini recente » Utilizatori inregistrati la preONI 2007, Runda 2, Clasa a 10-a | Cod sursa (job #1909881) | Borderou de evaluare (job #2116775) | Cod sursa (job #2488134) | Cod sursa (job #3249740)
#include <stdio.h>
#include <stdlib.h>
int baza=137;
int mod=(int)(1e9+7);
int put[2000001];
int v[2000001];
int ri[1000];
int ex(int a, int n){
if (n == 0) return 1;
if((n&1)==0){
int rasp=ex(a,n/2)%mod;
return (1ll*rasp*rasp)%mod;
}
else{
return (1ll*a*ex(a,n-1))%mod;
}
return 1;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int j=0,h=0,cnt=0;
put[0]=1;
for(int i=1;i<2000001;i++){
put[i]=(1ll*put[i-1]*baza)%mod;
}
char ch=fgetc(stdin);
while((ch==' '||ch=='\n')&&ch!=EOF)
ch=fgetc(stdin);
while(ch!=' '&&ch!='\n'&&ch!=EOF){
h=(1ll*h+1ll*put[j]*ch)%mod;
ch=fgetc(stdin);
j++;
}
while((ch==' '||ch=='\n')&&ch!=EOF)
ch=fgetc(stdin);
int i=0;
while(ch!=' '&&ch!='\n'&&ch!=EOF){
v[i]=(1ll*(1ll*put[i]*ch)%mod+1ll*(i>0?v[i-1]:0))%mod;
ch=fgetc(stdin);
i++;
};
int pp=0;
if(v[j-1]==h){
cnt++;
ri[pp++]=1;
}
for(int k=j;k<i;k++){
int s=(1ll*(v[k]-v[k-j]+mod)*ex(put[k-j+1], mod - 2))%mod;
if(s==h) {
cnt++;
if(pp<1000)
ri[pp++]=k-j+1;
}
};
printf("%d\n",cnt);
for(int m=0;m<pp;m++){
printf("%d ",ri[m]);
}
return 0;
}