Cod sursa(job #1550152)

Utilizator KOzarmOvidiu Badea KOzarm Data 13 decembrie 2015 12:27:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <cstring>

int m,n,p=73,p1,p2,i,a1,b1,a2,b2,MOD1=100007,MOD2=100021;
long long d;
char match[2000001],A[2000001],B[2000001];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",&A,&B);
    m=strlen(A);
    n=strlen(B);
    p1=p2=1;
    a1=a2=0;
    for (i=0; i<=m-1; i++)
    {
        a1=(a1*p+A[i])%MOD1;
        a2=(a2*p+A[i])%MOD2;
        b1=(b1*p+B[i])%MOD1;
        b2=(b2*p+B[i])%MOD2;
    if (i!=0)
    p1=(p1*p)%MOD1,
    p2=(p2*p)%MOD2;}
    if (m>n)
    {
        printf("0\n");
        return 0;
    }
    int Nr = 0;
    if(b1==a1&&b2==a2)match[0]=1,Nr++;
    for (int i = m; i < n; i++)
    {
        b1=((b1-(B[i-m]*p1)%MOD1+MOD1)*p+B[i])%MOD1;
        b2=((b2-(B[i-m]*p2)%MOD2+MOD2)*p+B[i])%MOD2;
            if (b1==a1&&b2==a2)
                match[i-m+1]=1, Nr++;
    }
    printf("%d\n",Nr);
    Nr = 0;
    for(int i = 0; i < n && Nr < 1000; i++)
    if(match[i]) Nr++, printf("%d ",i);
    printf("\n");
    return 0;
    }