Cod sursa(job #3249740)

Utilizator TheodosiusOancea Teodor Stefan Theodosius Data 17 octombrie 2024 16:50:52
Problema Potrivirea sirurilor Scor 38
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#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;
}