Cod sursa(job #1402374)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 26 martie 2015 15:40:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define nmax 2000001
#define mod1 100009
#define mod2 100079
#define p 57
using namespace std;
FILE *f=fopen("strmatch.in","r"),*g=fopen("strmatch.out","w");
int ha1,ha2,h1,h2,k,r[1001];
char a[nmax],b[nmax];
int main()
{
    int i,j,la,lb,p1=1,p2=1;
    fscanf(f,"%s %s",a,b);
    la=strlen(a);
    lb=strlen(b);
    for(i=0;i<la;i++)
    {
        ha1=(ha1*p+a[i])%mod1;
        ha2=(ha2*p+a[i])%mod2;
        if(i!=0)
            p1=(p1*p)%mod1,
            p2=(p2*p)%mod2;
    }
    for(i=0;i<la;i++)
    {
        h1=(h1*p+b[i])%mod1;
        h2=(h2*p+b[i])%mod2;
    }
    if(h1==ha1&&h2==ha2)
        r[++k]=0;
    for(i=la;i<lb;i++)
    {
        h1=((h1-(b[i-la]*p1)%mod1+mod1)*p+b[i])%mod1;
        h2=((h2-(b[i-la]*p2)%mod2+mod2)*p+b[i])%mod2;

        if(h1==ha1&&h2==ha2)
        {
            k++;
            if(k<=1000)
                r[k]=i-la+1;
        }
    }
    fprintf(g,"%d\n",k);
    for(i=1;i<=min(k,1000);i++)
        fprintf(g,"%d ",r[i]);
    fclose(f);
    fclose(g);
    return 0;
}