Cod sursa(job #1098379)

Utilizator costyrazvyTudor Costin Razvan costyrazvy Data 4 februarie 2014 19:34:55
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <cstring>
using namespace std;
int val[3],txt[3],mod[3],bz[3],na,nb,i,sol[2000001],nr,k;
char a[2000001],b[2000001];
int min(int a,int b)
{
    if (a>b) return b;
    return a;
}
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    mod[1]=666013;mod[2]=10003;
    na=strlen(a);
    bz[1]=1;
    bz[2]=1;
    nr=0;
    for (i=0;i<na;i++)
    {
        val[1]=(val[1]*101%mod[1]+b[i])%mod[1];
        val[2]=(val[2]*109%mod[2]+b[i])%mod[2];
        txt[1]=(txt[1]*101%mod[1]+a[i])%mod[1];
        txt[2]=(txt[2]*109%mod[2]+a[i])%mod[2];
        if(i!=0)
        {
            bz[1]=(bz[1]*101)%mod[1];
            bz[2]=(bz[2]*109)%mod[2];
        }
    } k=0;
    if (txt[1]==val[1] && txt[2]==val[2]) sol[++k]=0,nr++;
    nb=strlen(b);
    for (i=na;i<nb;i++)
    {
           val[1]=( (val[1]-(b[i-na]*bz[1])% mod[1] + mod[1])*101 + b[i])%mod[1];
           val[2]=( (val[2]-(b[i-na]*bz[2])% mod[2] + mod[2])*109 + b[i])%mod[2];
            if (val[1]==txt[1] && val[2]==txt[2])
            sol[++k]=i-na+1,nr++;
    }
    printf("%d",nr);
    for (i=1;i<=min(1000,k);i++)  printf("%d ",sol[i]);
    return 0;
}