Cod sursa(job #831619)

Utilizator lianaliana tucar liana Data 8 decembrie 2012 20:50:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<stdio.h>
#include<cstring>
using namespace std;
#define p1 666013
#define p2 666019
#define baz 130
#define lgmax 2000005
long nra1, nra2, nrb1, nrb2, rez, v[1005], pbaz1, pbaz2, i, la, lb;
char a[lgmax], b[lgmax];
 
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",a);  scanf("%s",b);
    la=strlen(a);   lb=strlen(b);
    if (la<=lb)
    {
        for (i=0;i<la;i++)
        {  
            nra1=(nra1*baz+a[i])%p1;    nra2=(nra2*baz+a[i])%p2;   
            nrb1=(nrb1*baz+b[i])%p1;    nrb2=(nrb2*baz+b[i])%p2;   
        }
        if ((nra1==nrb1)&&(nra2==nrb2))
            v[++rez]=0;
         
        pbaz1=pbaz2=1;
        for (i=1;i<=la-1;i++)
        {   pbaz1=(pbaz1*baz)%p1;   pbaz2=(pbaz2*baz)%p2;       }
         
        for (i=la;i<lb;i++)
		{
            nrb1=nrb1-(b[i-la]*pbaz1)%p1;
            if (nrb1<0)
                nrb1+=p1;
            nrb1=(nrb1*baz+b[i])%p1;
             
            nrb2=nrb2-(b[i-la]*pbaz2)%p2;
            if (nrb2<0)
                nrb2+=p2;
            nrb2=(nrb2*baz+b[i])%p2;
             
            if ((nra1==nrb1)&&(nra2==nrb2))
            {
                rez++;
                if (rez<=1000)
                    v[rez]=i-la+1;
            }
        }
     
        printf("%ld\n",rez);
        for (i=1;i<=rez;i++)
        {
            printf("%ld ",v[i]);
            if (i==1000)
                break;
        }
    }  
    else
        printf("0");
	return 0;
}