Cod sursa(job #1098383)

Utilizator costyrazvyTudor Costin Razvan costyrazvy Data 4 februarie 2014 19:42:00
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <cstring>
#define mod1 666013
#define mod2 10003
using namespace std;
int val[3],txt[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()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",a);
    scanf("%s",b);
    na=strlen(a);
    bz[1]=1;
    bz[2]=1;
    nr=0;
    for (i=0;i<na;i++)
    {
        val[1]=(val[1]*101%mod1+b[i])%mod1;
        val[2]=(val[2]*109%mod2+b[i])%mod2;
        txt[1]=(txt[1]*101%mod1+a[i])%mod1;
        txt[2]=(txt[2]*109%mod2+a[i])%mod2;
        if(i!=0)
        {
            bz[1]=(bz[1]*101)%mod1;
            bz[2]=(bz[2]*109)%mod2;
        }
    } 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])% mod1 + mod1)*101 + b[i])%mod1;
           val[2]=( (val[2]-(b[i-na]*bz[2])% mod2 + mod2)*109 + b[i])%mod2;
            if (val[1]==txt[1] && val[2]==txt[2])
            sol[++k]=i-na+1,nr++;
    }
    printf("%d\n",nr);
    for (i=1;i<=min(1000,k);i++)  printf("%d ",sol[i]);
    return 0;
}