Cod sursa(job #1551149)

Utilizator razvanlgu31Razvan Lungu razvanlgu31 Data 15 decembrie 2015 11:06:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <cstring>
#define p 73
#define MAXN 2000001
#define m1 100007
#define m2 100021
using namespace std;
char A[MAXN],B[MAXN],C[MAXN];
int n,a1,b1,a2,b2,nr,na,nb,i,ver=0;
long long p1=1,p2=1;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",&A,&B);
    na=strlen(A);
    nb=strlen(B);
    a1=a2=0;
    for(i=0; i<na; i++)
    {
        a1=(a1*p+A[i])%m1;
        a2=(a2*p+A[i])%m2;
        if(i!=0)
        {
            p1=(p1*p)%m1;
            p2=(p2*p)%m2;
        }
    }
     if(na>nb)
    {
        printf("0\n");
        return 0;
    }
    b1=b2=0;
     for(i=0; i<na; i++)
    {
        b1=(b1*p+B[i])%m1;
        b2=(b2*p+B[i])%m2;
    }
    if(a1==b1 && a2==b2)
    {
        C[0]=1;
        nr++;
    }
    for(i=na; i<nb; i++)
    {
        b1=((b1-(B[i-na]*p1)%m1+m1)*p+B[i])%m1;
        b2=((b2-(B[i-na]*p2)%m2+m2)*p+B[i])%m2;
        if(a1==b1 && a2==b2)
        {
            C[i-na+1]=1;
            nr++;
        }
    }
    printf("%d\n",nr);
    nr=0;
    for(i=0; i<nb && nr<1000; i++)
        if(C[i]==1)
        {
            printf("%d ",i);
            nr++;
        }
    return 0;
}