Cod sursa(job #803852)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 28 octombrie 2012 14:04:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<cstring>
#define d 73
#define mod1 100007
#define mod2 100021
#define NMax 2000005
using namespace std;

int sir1,sir2,model1,model2,h1=1,h2=1,sol[NMax],m,n;
char p[NMax],s[NMax];

int main ()
{
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",p);
    scanf("%s",s);
    m=strlen(p);
    n=strlen(s);
    if (m>n)
    {
        printf("0");
        return 0;
    }
    for (i=0; i<m; i++)
    {
        model1=(model1*d+p[i])%mod1;
        model2=(model2*d+p[i])%mod2;
        if (i)
        {
            h1=(h1*d)%mod1;
            h2=(h2*d)%mod2;
        }
        sir1=(sir1*d+s[i])%mod1;
        sir2=(sir2*d+s[i])%mod2;
    }
    for (i=0; i<=n-m; i++)
    {
        if (model1==sir1 && model2==sir2)
            sol[++sol[0]]=i;
        if (i<n-m)
        {
            sir1=(d*(sir1-(s[i]*h1)%mod1+mod1)+s[i+m])%mod1;
            sir2=(d*(sir2-(s[i]*h2)%mod2+mod2)+s[i+m])%mod2;
        }
    }
    printf("%d\n",sol[0]);
    for (i=1; i<=sol[0]; i++)
        printf("%d ",sol[i]);
    return 0;
}