Cod sursa(job #2781188)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 8 octombrie 2021 18:38:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>
#include<cstring>
typedef unsigned long long L;
const int U=2000001,V=1000,B=29;
int m[V],r,N,M,i,l;
char b[U];
L C=1,H,R;
int main()
{
    freopen("strmatch.in","r",stdin),freopen("strmatch.out","w",stdout),
    scanf("%s",b),M=strlen(b);
    for(i=1;i<=M;++i)
        C*=B;
    for(i=0;i<M;++i)
        H=H*B+b[i];
    scanf("%s",b),N=strlen(b);
    if(N<M) {
        puts("0");
        return 0;
    }
    for(i=0;i<M;++i)
        R=R*B+b[i];
    for(i=M;;++i) {
        if(R==H) {
            if(r<V)
                m[r]=i-M;
            ++r;
        }
        if(i==N)
            break;
        R=R*B+b[i]-b[i-M]*B;
    }
    printf("%d\n",r);
    for(i=0,l=(r<V?r:V);i<l;++i)
        printf("%d ",m[i]);
    return 0;
}